- #1
CGandC
- 326
- 34
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 )
## 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: