Week 12: A Fun Induction Problem

Introducing a Fellow Slogger:

            Please note that this is not a problem solving episode (see Week 9).  This final week, the instructors introduce simple induction.  A fellow slogger gives a nice induction post under Week 12 here.

http://pythoncodeshark.wordpress.com/

You can also find my comments to the following slog under Week 3:

http://sosocompsci.blogspot.ca/

            What is really cool about the induction post is that the slogger talks about how induction is used in a proof of the following statement: the determinant of any $n \times n$ identity matrix is $1$.  In fact, I am so excited that a fellow slogger uses CSC165 concepts for greater and better things that I feel compelled to follow the slogger's footsteps.  I will also use CSC165 concepts as a guide for a problem that is outside the scope of this course:

The Fun Problem:

            Problem:  Is the following statement true: the determinant of any upper triangular matrix is
            the product of its diagonal entries?

The truth is I have no clue.  In my Problem Solving Episode under Week 9 (under the heading Step 1: Understand the Problem), I work out examples of an idea that I do not fully understand to gain intuition.  We should work out examples for this problem too.

            First we know that an upper triangular matrix is a $n \times n$ matrix $A$ that is defined by:

$A_{ij} = \begin{cases} a_{ij} & i \leq j \\ 0 & i > j \end{cases}$.

Then the following matrices satisfy the definition nicely:

$\begin{bmatrix} 1 & 2 \\ 0 & 3 \end{bmatrix}, \begin{bmatrix} 4 & 5 & 6 \\ 0 & 7 & 8 \\ 0 & 0 & 9 \end{bmatrix}$.

Secondly, let $A$ be a $n \times n$ matrix and $F$ be a field.   Then the determinant is a function $det: M_{n \times n}(F) \to F$ that is defined by:

$det(A) = \begin{cases} A_{ij} & n = 1 \\ \sum\limits_{j= 1}^n (-1)^{i + j} A_{ij} det(\bar{A_{ij}}) & n \geq 2 \end{cases}$.

There is some fancy notation here but it is not difficult to understand.  For simplicity sakes, think of $F$ as the set of real numbers.  Also, the strange bar on top of $A_{ij}$ just means $A$ with both row $i$ and column $j$ removed.  We see that the determinant is recursively defined.  This may be useful later.

            To find the determinant of the above matrices, use the definition.  For the $2 \times 2$ matrix, we have:

$det(\begin{bmatrix} 1 & 2 \\ 0 & 3 \end{bmatrix}) = (-1)^{1 + 1}(1)(3) + (-1)^{1 + 2}(0) = 3$.

For the $3 \times 3$ matrix, we have:

$det(\begin{bmatrix} 4 & 5 & 6 \\ 0 & 7 & 8 \\ 0 & 0 & 9\end{bmatrix}) =$

$(-1)^{1 + 1}(4)det(\begin{bmatrix} 7 & 8 \\ 0 & 9 \end{bmatrix}) + (-1)^{1 + 2}(5)det(\begin{bmatrix} 0 & 8 \\ 0 & 9 \end{bmatrix}) + (-1)^{1 + 3}(6)det(\begin{bmatrix} 0 & 7 \\ 0 & 0 \end{bmatrix}) =$

$(4)(-1)^{1 + 1}(7)(8) + (-1)(5)(-1)^{1 + 1}(0)(9) + (5)(-1)^{1 + 1}(0)(0) =$

$(4)(7)(8) + 0 + 0 = 224$.

It seems like the statement is true and that we should try proving it.  Something interesting in the calculation is that the determinant of a matrix with a column of $0$s is $0$.  Again, this may be useful later.

The Attempt at a Solution:

            How should we prove the statement?  A direct proof comes to mind but remember that the determinant is recursively defined.  This makes it difficult to work with unless we know the determinant of a previous recursive case.  Proof by simple induction sounds attractive here.  The induction hypothesis may give us the determinant of a previous recursive case.  Let us try it.

            Since a $0 \times 0$ matrix is undefined, then we show that $\forall n \in N, n \geq 1 \implies$ the determinant of an upper triangular $n \times n$ matrix is the product of its diagonal entries.  By simple induction on $n$, we show that this statement is true.  The CSC165 proof structure for induction is our guide.

            For the base case, assume that $n = 1$.  Let $A$ be a $1 \times 1$ upper triangular matrix.  By the definition of the determinant, then $det(A) = A_{ij}$.  Since $A_{ij}$ is the only diagonal entry, then statement is true for $n = 1$.

            For the induction step, assume that $n \in N, n \geq 1$ and that the statement is true for $n$.  That will be our induction hypothesis.  We need to show that the statement is true for $n + 1$.  Let $A$ be a $(n + 1) \times (n + 1)$ upper triangular matrix.   By the definition of the determinant, we have that

$det(A) =  \sum\limits_{j = 1}^{n + 1} (-1)^{1 + j}A_{1j} det(\bar{A_{1j}})$.

            Remember this observation: the determinant of a matrix with a column of $0$s is $0$?  Turns out, that is because a square matrix with a column of $0$s is not invertible and some fancy theorem tells us that the determinant of such a matrix is $0$.

            Luckily, we make the following observation:

$det(A) = \sum\limits_{j = 1}^{n + 1} (-1)^{1 + j} A_{1j} det(\bar{A_{1j}}) =  (-1) ^{1 + 1}A_{11} det(\bar{A_{11}}) +  \sum\limits_{j = 2}^{n + 1} (-1)^{1 + j}A_{1j} det(\bar{A_{1j}})$.

Notice that the matrix $\bar{A_{1j}}$ is $A$ without row $1$ and without a column $j \geq 2$.  Minus the first element, column $1$ of $A$ is a column of $0$s  So the matrix $\bar{A_{1j}}$ also has a column of $0$s.  Thus, $det(\bar{A_{1j}}) = 0$  and

$det(A) = (-1) ^{1 + 1}A_{11} det(\bar{A_{11}}) +  \sum\limits_{j = 2}^{n + 1} (-1)^{1 + j}A_{1j} det(\bar{A_{1j}}) = (-1) ^{1 + 1}A_{11} det(\bar{A_{11}})$.

            The matrix $\bar{A_{11}}$ has both row $1$ and column $1$ removed but it is still an upper triangular $n \times n$ matrix.  By the induction hypothesis, then $det(\bar{A_{11}})$ is the product of its diagonal entries.  Notice that the diagonal entries of $det(\bar{A_{11}})$  are the diagonal entries of $A$ without $A_{11}$.  Since

$det(A) = (-1) ^{1 + 1}A_{11} det(\bar{A_{11}}) =  A_{11} det(\bar{A_{11}})$,

then we have $det(A)$ as the product of its diagonal entries.  Since $A$ is a $(n + 1) \times (n + 1)$ upper triangular matrix, then the statement is true for $n + 1$.  By simple induction, then $\forall n \in N, n \geq 1 \implies$ the statement is true for $n$.  So that is my attempt is at this fun problem.