Det of Triangular-like Matrix & getting stuck in Algorithmic Proof

[CGandC]

Find determinant of following matrix:
$A = \begin{pmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n-1} & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n-1} & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{n,1} & 0 & \cdots & 0 & 0 \end{pmatrix}$

Note: I tried to solve this question by permutations, and the formula for determinant of any square matrix A by permutations is : $detA = \sum_{\sigma \in S_n} sgn(\sigma)a_{1,\sigma(1)} \cdots a_{n,\sigma(n)}$
Attempt:
Lemma 1: there's only 1 permutation for the given matrix A, for which $detA \neq 0$ and that is: $\sigma = \begin{pmatrix} 1 & 2 & \cdots & n-1 & n \\ n & n-1 & \cdots & 2 & 1 \\ \end{pmatrix}$
Lemma 2: for the given matrix A , $sgn(\sigma) = (-1)^{ \frac{n}{2} (n+3)}$

So, $detA = \sum_{\sigma \in S_n} sgn(\sigma)a_{1,\sigma(1)} \cdots a_{n,\sigma(n)} = sgn(\sigma) \prod_{k=1}^{n}a_{k,n-(k-1)} = (-1)^{ \frac{n}{2} (n+3)} a_{1,n} a_{2,n-1} \cdots a_{n-1,2} a_{n,1}$ and that's it.

My attempt of Proof of lemma 1:
Let $\sigma \in S_n$ be arbitrary.
If $\sigma(n) \neq 1$ then $a_{n,\sigma(n)} = 0$ and then $sgn(\sigma)a_{1,\sigma(1)} \cdots a_{n,\sigma(n)} = 0$ . Else if $\sigma(n) = 1$ then $a_{n,\sigma(n)} = a_{n,1}$ . So the only permutations that participate in the sum are those where $\sigma(1) = n$
It follows that $\sigma(n-1) = 2$ since otherwise, it can't be that $\sigma(n-1) = 1 ( \text{ since \sigma is one-to-one } )$ and if $\sigma(n-1) \neq 2, 1$ , then clearly $a_{n-1,\sigma(n-1)} = 0$ and so $sgn(\sigma)a_{1,\sigma(1)} \cdots a_{n,\sigma(n)} = 0$ . So the only permutations that participate in the sum are those where $\sigma(1) = n$ and $\sigma(2) = n-1$.
Continuing in this fashion until we reach $\sigma(1)$ , we'll show for every $k \in \mathbb{N} \text{ s.c. } k \leq n$ , that $\sigma(k) = n-(k-1)$
My attempt of Proof of lemma 2:
$$ |B| = sgn(\sigma) = \begin{vmatrix}
0 & 0 & \cdots & 0 &1 \\
0 & 0 & \cdots & 1 &0 \\
& & \vdots & & \\
0 & 1 & \cdots & 0 &0 \\
1 & 0 & \cdots & 0 &0 \notag
\end{vmatrix} = \sum_{j=1}^{n}(-1)^{j+1}b_{1,j}|B_{1,j}| = (-1)^{n+1}|B_{1,j}| =
\underbrace{...}_{\begin{subarray}{l}\text{ each time we'll expand the determinant }\\
\text{of the matrix in the multiplication} \\ \text{by the first row until we reach a } \\ \text{determinant of a matrix of size 1 } \end{subarray}} = (-1)^{\sum_{k=1}^{n}n+2-k} = (-1)^{ \frac{n}{2} (n+3)} $$

My difficulty :
My attempt of proof of both lemma's 1 & 2 is sort of algorithmic ( for proof of lemma 1 I say " Continuing in this fashion until we reach ... " & for proof of lemma 2 I say " each time ... until ... " ). At start I wanted to give a proof by induction for both these lemma's but I didn't know how to apply induction for them. Algorithmic proof felt the way to go but I feel there are some lacking steps, and that I need to prove more things, like:

In proof of lemma 1, I essentially say:
" for each iteration of k ( for each $\sigma(k)$ ) we prove that $\sigma(k) = n-(k-1)$ "

Was this incorrect? ( to say in each iteration we prove something for that specific iteration )
Am I supposed to do the proof in each iteration? If so how? ( I think induction could be used to prove lemma 1 but It was too difficult for me to even see how to do it in this case )

In proof of lemma 2, I essentially say:
$|B| = sgn(\sigma) = (-1)^{n+1}|B_{1,j}| = \cdots = (-1)^{ \frac{n}{2} (n+3)}$

How do I actually prove that whatever happens in the " $\cdots$ " leads me to $(-1)^{ \frac{n}{2} (n+3)}$ ? I feel induction is needed on this but seems very hard to apply ( I think some sort of induction going down instead of up )

I felt here that the boundary between inductive and algorithmic proofs are not entirely clear, what's essentially the difference? ( I think inductive proof continues infinitely whereas algorithmic proof continues finitely up to some number )

 

[fresh_42]

Allow me one question before I start to dig into your long post: Why don't you use the formula with the adjugate matrices (Laplace expansion along the last column(s)), or likewise simply concentrate on all diagonals in your formula which are not zero?

 

[CGandC]

I haven't learned about adjugate matrices, but I did concentrate on the diagonals ( actually the mirrored diagonal ), In lemma 1 I tried to prove that contribution to the determinant only comes from the diagonals but the proof's tricky because for each diagonal element $k$ I have to prove $\sigma(k) = n - ( k - 1 )$ and that's where I got stuck ( "My attempt of proof of lemma 1 " ) so I proposed some sort of algorithm which for step $k$ we prove $\sigma(k) = n - ( k - 1 )$ and wanted to know if I could do something like this ( and I still have problems with this method ) . Maybe Induction could work on this part but looks really hard to apply ( Maybe it's not even simple induction )

 

[suremarc]

I don’t understand your statement of Lemma 1:

Lemma 1: there's only 1 permutation for the given matrix A, for which $detA \neq 0$ and that is: $\sigma = \begin{pmatrix} 1 & 2 & \cdots & n-1 & n \\ n & n-1 & \cdots & 2 & 1 \\ \end{pmatrix}$

Are you saying there’s only 1 permutation of the columns of $A$ s.t. $\det A\neq 0$? Permutations only change the determinant by a factor of $\pm 1.$

Secondly, I don’t know if the formula for $\mathrm{sgn}(\sigma)$ is correct. It should be $(-1)^{\lfloor\frac{n}{2}\rfloor}$, because the desired permutation is equivalent to $\lfloor\frac{n}{2}\rfloor$ swaps.

Instead of trying to use the Leibniz formula, I would advise you to learn about elementary row operations and cofactor expansions. The Leibniz formula just makes a simple problem like this obscure.

 

[fresh_42]

I haven't learned about adjugate matrices, but I did concentrate on the diagonals ( actually the mirrored diagonal )

A diagonal in this context is one element of each row and each column, the $a_{1,\sigma(1)}\cdot\ldots\cdot a_{n,\sigma(n)}$ in your formula. We need all $a_{k,\sigma(k)}\neq 0$ in order to count. There is only one possibility for $\sigma.$ I assume that is what you meant in Lemma 1.

Well, nobody will complain if you just say which $\sigma$ this is, but formally, you could do an induction proof starting at the bottom, the $n-$th row.

 

[CGandC]

Secondly, I don’t know if the formula for $\mathrm{sgn}(\sigma)$ is correct. It should be $(-1)^{\lfloor\frac{n}{2}\rfloor}$, because the desired permutation is equivalent to $\lfloor\frac{n}{2}\rfloor$ swaps.

They seem to be giving the same values in this case ( maybe I'm mistaken ). The way I reached the formula is:
$|B| = sgn(\sigma) = \begin{vmatrix} 0 & 0 & \cdots & 0 &1 \\ 0 & 0 & \cdots & 1 &0 \\ & & \vdots & & \\ 0 & 1 & \cdots & 0 &0 \\ 1 & 0 & \cdots & 0 &0 \notag \end{vmatrix} = \sum_{j=1}^{n}(-1)^{j+1}b_{1,j}|B_{1,j}| = (-1)^{n+1}|B_{1,n}|$define $B_{1,n} := C$ ( Note: C is $(n-1) \times (n-1)$ matrix )
$|B_{1,n}| = |C| = \sum_{j=1}^{n-1}(-1)^{j+1}c_{1,j}|C_{1,j}| = (-1)^{n}|C_{1,n-1}|$

define $C_{1,n-1} := D$ ( Note: D is $(n-2) \times (n-2)$ matrix )
$|C_{1,n}|= |D| = \sum_{j=1}^{n-2}(-1)^{j+1}d_{1,j}|D_{1,j}| = (-1)^{n-1}|D_{1,n-2}|$

define $D_{1,n-2} := E$ ( Note: E is $(n-3) \times (n-3)$ matrix )
$D_{1,n-2}= |E| = \sum_{j=1}^{n-3}(-1)^{j+1}e_{1,j}|E_{1,j}| = (-1)^{n-2}|E_{1,n-3}|$
.
.
.
We continue the process until we reach a determinant of a matrix of size 1x1 and there we stop.

Eventually we get:

$|B| = sgn(\sigma) = (-1)^{n+1}|B_{1,n}| = (-1)^{n+1} \cdot (-1)^{n} \cdot (-1)^{n-1} \cdot (-1)^{n-2} \cdots (-1)^2 = (-1)^{\sum_{k=1}^{n}n+2-k} = (-1)^{ n(n+2) - \frac{n}{2}(n+1) } = (-1)^{ \frac{n}{2} (n+3)}$

There is only one possibility for $\sigma.$ I assume that is what you meant in Lemma 1.

Yes! , that's exactly what I meant to say.

Well, nobody will complain if you just say which $\sigma$ this is, but formally, you could do an induction proof starting at the bottom, the $n-$th row.

Suppose I want to do a proof by induction, would proving the following theorem prove the only possibility for $\sigma$ ?:

Theorem: For all nxn matrices $A$ . If $A = \begin{pmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n-1} & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n-1} & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{n,1} & 0 & \cdots & 0 & 0 \end{pmatrix}$ then there's only one possibility for $\sigma$ and that is $\sigma = \begin{pmatrix} 1 & 2 & \cdots & n-1 & n \\ n & n-1 & \cdots & 2 & 1 \\ \end{pmatrix}$ .

The proof of this seems to me like applying simple induction.

 

[fresh_42]

Theorem: For all nxn matrices $A$ . If $A = \begin{pmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n-1} & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n-1} & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{n,1} & 0 & \cdots & 0 & 0 \end{pmatrix}$ then there's only one possibility for $\sigma$ and that is $\sigma = \begin{pmatrix} 1 & 2 & \cdots & n-1 & n \\ n & n-1 & \cdots & 2 & 1 \\ \end{pmatrix}$ .

The proof of this seems to me like applying simple induction.

Yes, if you start at the bottom row which only has $a_{n,1}$ as non-zero element. But I wouldn't say 'only one possibility for $\sigma$'. This is the wrong phrasing, since $\sigma$ runs through the entire permutation group. What you want to say is
$$
a_{1,\sigma(1)}\cdot\ldots\cdot a_{n,\sigma(n)} \neq 0 \Longrightarrow \sigma=\prod_{k=1}^{\lfloor n/2\rfloor}(k\,,\,(n-k+1))
$$

 

[CGandC]

Thinking more about this, to calculate detA, I can do the following:
If $n$ is even then we perform $n/2$ row swaps ( $R_i \iff R_{n-i+1}$ ) and we get that $sgn(\sigma) = (-1)^{n/2}$.
If $n$ is odd then we perform $\frac{n-1}{2}$ row swaps ( excluding middle row ) and we get that $sgn(\sigma) = (-1)^{\lfloor n/2\rfloor}$
And so, $detA = sgn(\sigma) a_{1,\sigma(1)}\cdot\ldots\cdot a_{n,\sigma(n)}$ ( we substitute the appropriate expression for $sgn(\sigma)$ depending whether $n$ is even or not.

And each of the above if's can be proved by induction.
_ _ _ _ _ _ _ _ _ _
I want to propose something different, I wrote a pseudo-code to calculate the determinant:

* denote the Routine that calculates $sgn(\sigma)$ as SIGN_SIGMA(A) where A is the given matrix.

* then the routine that calculates the determinant is:

If n is even then,
z // we perform n/2 row swaps
zz for i=1 to n/2
zzzz swap $R_i$ with $R_{n-i-1}$
zz sgn_sigma = SIGN_SIGMA(A)
Else,
z // we perform k row swaps ( without middle row)
zz for i=1 to (n-1)/2
zzzz swap $R_i$ with $R_{n-1-1}$
zz sgn_sigma = SIGN_SIGMA(A)
detA = sgn_sigma $\cdot a_{1,\sigma(1)}\cdot\ldots\cdot a_{n,\sigma(n)}$

If I were to prove the correctness of this algorithm ( which needs a bit of tidying up and being more precise ), would you consider this algorithm as a proof for the calculation of $det A$ ?

 

[fresh_42]

If n is even then,
z // we perform n/2 row swaps
zz for i=1 to n/2
zzzz swap $R_i$ with $R_{n-i-1}$
zz sgn_sigma = SIGN_SIGMA(A)
Else,
z // we perform k row swaps ( without middle row)
zz for i=1 to (n-1)/2
zzzz swap $R_i$ with $R_{n-1-1}$
zz sgn_sigma = SIGN_SIGMA(A)
detA = sgn_sigma $\cdot a_{1,\sigma(1)}\cdot\ldots\cdot a_{n,\sigma(n)}$

If I were to prove the correctness of this algorithm ( which needs a bit of tidying up and being more precise ), would you consider this algorithm as a proof for the calculation of $\det A$ ?

I haven't analyzed it in detail, but the answer is yes. However, there are several points to consider, which IMO a more than a bit tidying up. You have to prove, that:

• the algorithm stops
• the algorithm does what you claim it does
• such a proof has to be done by using a recursion, which is no different from a proof by induction
• ideally add an estimation of runtime and space

In the end you will have done one special permutation. A task, by the way, which can more easily be done by suited matrix multiplications. And since the determinant is multiplicative, this would be sufficient. Furthermore, as the algorithm solves only one problem, you could as well consider algorithms which calculate arbitrary determinants: Gram-Schmidt, Jordan, Gauß, etc.

For the specific problem, it is far easier to simply look at
$$
\{a_{1\sigma (1)}\cdot\ldots\cdot a_{n\sigma (n)}\,|\,a_{1\sigma (1)}\cdot\ldots\cdot a_{n\sigma (n)}\neq 0\, , \,\sigma \in \operatorname{Sym}(n)\}
$$
which has only one element, i.e. your sum has only one term, with the correct factor $\operatorname{sgn}(\sigma ).$