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

• CGandC
In summary: My answer:The reason I chose to use permutations in my attempt is because the question mentioned that the person was trying to solve the problem using permutations. However, using the formula with adjugate matrices or focusing on diagonals would also be valid approaches to solving the problem. It ultimately depends on the individual's preference and understanding of the topic.
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 )

Last edited by a moderator:
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?

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 )

I don’t understand your statement of Lemma 1:
CGandC said:
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.

CGandC said:
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.

suremarc said:
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)}

##
fresh_42 said:
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.

fresh_42 said:
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.

CGandC said:
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
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 ## ?

CGandC said:
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 ).##

CGandC

## 1. What is a triangular-like matrix?

A triangular-like matrix is a square matrix where all elements above or below the main diagonal are either zero or follow a specific pattern. Examples of triangular-like matrices include upper triangular, lower triangular, and diagonal matrices.

## 2. How is the determinant of a triangular-like matrix calculated?

The determinant of a triangular-like matrix can be calculated by simply multiplying the elements on the main diagonal. For example, the determinant of an upper triangular matrix is the product of its diagonal elements.

## 3. Why do we get stuck in algorithmic proofs when trying to solve for the determinant of a triangular-like matrix?

Algorithmic proofs can become complex and difficult to follow when dealing with triangular-like matrices because of the many possible patterns and exceptions that must be considered. This can lead to errors and getting stuck in the proof process.

## 4. How can we avoid getting stuck in algorithmic proofs for triangular-like matrix determinants?

One way to avoid getting stuck in algorithmic proofs is to use a systematic approach, such as using matrix operations to simplify the matrix before attempting to find the determinant. Additionally, having a thorough understanding of matrix properties and patterns can also help in navigating algorithmic proofs.

## 5. Are there any shortcuts or tricks for finding the determinant of a triangular-like matrix?

Yes, there are some shortcuts and tricks that can be used to find the determinant of a triangular-like matrix. For example, for a lower triangular matrix, the determinant can be found by simply multiplying the elements on the main diagonal and then taking the absolute value of the result. However, these shortcuts may not always work for more complex matrices, so it is important to have a strong understanding of matrix properties and patterns.

• Math Proof Training and Practice
Replies
6
Views
1K
• Math Proof Training and Practice
Replies
10
Views
1K
• Math Proof Training and Practice
Replies
61
Views
6K
• Math Proof Training and Practice
Replies
25
Views
2K
• Linear and Abstract Algebra
Replies
3
Views
1K
• Math Proof Training and Practice
Replies
19
Views
1K
• Precalculus Mathematics Homework Help
Replies
2
Views
951
• Linear and Abstract Algebra
Replies
15
Views
4K
• Calculus and Beyond Homework Help
Replies
4
Views
1K
• Mechanical Engineering
Replies
9
Views
1K