Closure of Upper Triangular Matrix Multiplication

24 Nov 2022

Given two \(n \times n\) upper triangular matrices \(A\) and \(B\), I show that \(A * B\) is also upper triangular without using induction.

Proof

For matrix \(A\) to be upper triangular, \(A_{ij} = 0\) for \(i > j\) by definition. Similar, this also is required of \(B\). We want to show that \(A * B\) also has this property.

First, let’s rewrite this property as \(A_{ij} = 0\) for \(i \geq j + 1\), as both \(i\) and \(j\) are integers (it does not make sense to have a non-integer entry in a matrix, at least as far as I know).

Rearranging \(i \geq j+1\), we get:

\[i - 1 - j \geq 0\] \[i - 1 - j + n \geq n\] \[(i - 1) + (n - j) \geq n\]

This will be true for any entry in \(AB_{ij}\) whenever \({i \geq j+1}\), which is precisely the entries we want to check are zero!

Now we use the row-column definition of matrix multiplication. If \(AB_{ij} = 0\), then \(row_i(A) \cdot col_j(B) = 0\).

Because we know \(A\) and \(B\) to be upper triangular, \(row_i(A)\) starts with \(i-1\) zero entries (assume 1-indexing). Also, \(col_j(B)\) ends in \(n-j\) zero entries.

From the rearrangement, we can conclude the number of zero entries at the beginning of \(row_i(A)\) and the number of zero entries at the end of \(col_j(B)\) sum to at least \(n\), which is the length of both \(row_i(A)\) and \(col_j(B)\).

Thus, the dot product will consist of a sum of products with at least one zero in every product. Further, whenever \((i-1) + (n-j) >= n+1\), both operands in the product will be zero.

So, \(AB_{ij} = row_i(A) \cdot col_j(B) = \sum\limits_{i=0}^n 0 = 0\).

\(AB\) is upper triangular!

Extra

Happy Thanksgiving, friends.