- #1

CGandC

- 279

- 23

**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: