Let $A_1,A_2,\dots,A_d$ be $d\times d$ matrices that are strictly upper triangular. Then, the product of $A_1,A_2,\dots,A_d$ is the zero matrix.

Question

SOLUTION: Let $B_i$ be given by $A_1A_2\dots A_i$. It can be shown inductively that $B_i$ is also strictly triangular, but with at least $i$ zero rows and columns. Therefore, $B_d$ will be the zero matrix.

I can't quite wrap my head around this. I would expect that in fact, the product of any two strictly triangular matrices would be the $0$ matrix. And therefore any other matrix (can be non-zero) that is multiplied with it will be the $0$ matrix. But the answer seems to say that it only has at least $i$ zero rows and columns after multiplying $i$ strictly trangiangular matrices. It might be that I am misunderstanding the entire answer in general but any simplification explanation is welcomed.

SOURCE: Linear Algebra and Optimization for Machine Learning: A Textbook (Problem 1.23)

Answer 1

It is not true that the product of two upper triangular matrices is necessarily $0$. As an example, take $d = 4$ and $$ A_1 = A_2 = A_3 = A_4 = A = \pmatrix{0&1&0&0\\0&0&1&0\\0&0&0&1\\0&0&0&0}. $$ In a sense, this is the "classic" example of a strictly upper triangular matrix considered in the context of Jordan normal form. Notice what happens when we multiply these matrices: $$ A^2 = \pmatrix{0&0&1&0\\0&0&0&1\\0&0&0&0\\0&0&0&0}, \quad A^3 = \pmatrix{0&0&0&1\\0&0&0&0\\0&0&0&0\\0&0&0&0}, \quad A^4 = 0. $$ In a sense, what happens here is what happens in general: multiplying two upper-triangular matrices "pushes" the first non-zero "diagonal" further up. In fact, I recommend that you prove the following:

We will say that $A$ is "upper triangular of order k" if its entries are such that $a_{ij} = 0$ whenever $j < i+k$. Prove that if $A$ is upper-triangular of order $p$ and $B$ is upper-triangular of order $q$, then $AB$ is upper-triangular of order $p + q$.

This is a more precise version of the pattern observed in the solution. It is possible to prove this fairly quickly using only the definition of matrix multiplication. Once you prove this result, perhaps you'll be able to see how the full solution holds as a consequence.

---

In a more abstract sense, what upper-triangularity tells us about the transformation associated with the matrices $A_1,\dots,A_d$ is that there are subspaces $$ \{0\} = V_0 \subsetneq V_1 \subsetneq \cdots \subsetneq V_{n-1} \subsetneq V_n = \Bbb R^d $$ for which $A(V_i) \subseteq V_{i-1}$ for each $i = 1,\dots, n$. That is, for every $v \in V_i$, $Av$ is an element of $V_{i-1}$.

This gives us an alternative proof. For any vector $v \in \Bbb R^d = V_n$, $A_d v$ is an element of $V_{n-1}$. Similarly, $A_{d-1}(A_d v)$ is an element of $V_{n-2}$. Continuing in this fashion, we can conclude that $A_2 \cdots A_d v \in V_1$, so that $$ A_1 A_2 \cdots A_d v = A_1(A_2 \cdots A_d v) \in V_0 = \{0\}, $$ which is to say that $A_1 A_2 \cdots A_d v = 0$ for every vector $v$. It follows that $A_1 A_2 \cdots A_d = 0$.