I recently started working through the first pages of Artins "Algebra" that discuss matrix operations, but the subject is still new to me, so I hope my question is not too simple. I am trying to solve the following problem:
Let $A=(a_{ij})$ be an upper triangle matrix with $n$ rows and columns. Proof by induction that $A$ is a product of elementary matrices of Type 1.
(Type 1 is the elementary matrix of the form $L=I+aE_{ij}$ with $i\neq j$.)
The concept of induction is clear to me, but I have a hard time applying it to matrices. I think that I know what the product is for a given $n$, but I don't see how I can make this into a rigorous proof by induction.
For example:
$n=3$:
$$ A=\begin{pmatrix}
1 & 1 & 1 \\
0 & 1 & 1 \\
0 & 0 & 1 \\
\end{pmatrix}=\begin{pmatrix}
1 & 1 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{pmatrix}\begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 1 \\
0 & 0 & 1 \\
\end{pmatrix}=(I+1E_{12})(I+1E_{23}).$$
The main thing that confuses me is that $n$ determines the size of the matrix and since multiplication is not defined for matrices with different sizes, why is induction useful and how can it be applied?
Best Answer
The problem statement as it stands is false. E.g. it is impossible to express a singular triangular matrix as a product of elementary matrices, because elementary matrices are necessarily nonsingular.
Even if $A$ is nonsingular, the statement is still false, because the diagonal elements in every product of elementary matrices of type 1 are necessarily equal to 1, but this is not always the case in $A$.
The statement can be corrected, however, by requiring that $A$ is a nonsingular upper triangular matrix whose diagonal elements are all equal to $1$. Let $B$ be the trailing principal $(n-1)\times(n-1)$ submatrix of $A$. Then $$ A=\left[\begin{array}{c|c} 1&\begin{array}{ccc}a_{12}&\cdots&a_{1n}\end{array}\\ \hline \begin{array}{c}0\\ \vdots\\ 0\end{array}&B \end{array}\right] =\begin{bmatrix}1&0\\ 0&B\end{bmatrix} \left(I+a_{12}E_{12}\right)\cdots\left(I+a_{1n}E_{1n}\right). $$ Since $A$ is a nonsingular upper triangular matrix whose diagonal elements are all equal to $1$, so is $B$. So, if $B=T_1T_2\cdots T_m$ is a product of elementary matrices of type $1$, then $$ A= \begin{bmatrix}1&0\\ 0&T_1\end{bmatrix} \cdots\begin{bmatrix}1&0\\ 0&T_m\end{bmatrix} \left(I+a_{12}E_{12}\right)\cdots\left(I+a_{1n}E_{1n}\right) $$ is a product of elementary matrices of type $1$.