EBT-III matrices should be a key tool in your inventory

By reading this post you’ll be able to comprehend the basic mechanism behind the proof of

• LU decomposition
• Schur Inversion Lemma
• The Sherman-Morrison-Woodbury inversion formula
• Small perturbations can’t reduce rank (p216-217 of Meyer)
• Rank of a matrix equals the rank of its largest nonsingular submatrix (p214 of Meyer; see also Exercise 4.5.15)
• Characteristic polynomial of $AB$ and $BA$ is the same for square $A,B$ (see Exercise 7.1.19, 6.2.16 and eq. (6.2.1) of Meyer)
• And many more theorems and lemmas (a few listed by the end of this post)

First, let’s clarify what even is an EBT-III matrix. This is a definition that I made up by extending the definition of an Elementary matrix of Type-III, which is simply a matrix like
$$
\begin{pmatrix}1 & 0 & 0 \\
0 & 1 & 0 \\
\alpha & 0 & 1\end{pmatrix},
$$
i.e., a matrix that is obtained by modifying a single entry of an identity matrix. I call an Elementary Block-matrix of Type-III a matrix of the form
$$
\begin{pmatrix}
I & 0 \\ L & I
\end{pmatrix} \,\,\,\,\,\text{ or } \,\,\,\,\,
\begin{pmatrix}
I & U \\ 0 & I.
\end{pmatrix}
$$
In other words, a 2×2 block triangular matrix which has $I$ on its diagonals and one of the other two blocks is zero, $0$.

EBT-III matrices are so critical because they are the fundamental mechanism for manipulating block matrices
$$
\begin{pmatrix}
A & B \\ C & D
\end{pmatrix}.
$$
For example, we can say many things about the rank, the inverse, the positive definiteness of a block matrix by manipulating it with EBT-III matrices (more below). EBT-III matrices are also a useful mechanism for proofs beyond block matrices, such as the LU decomposition, as we’ll see below.

Before proceeding, let’s see why EBT-III matrices are so intuitive and useful. This was already discussed in this post, but let’s re-cap here for thoroughness. An Elementary matrix of Type-III (which is a special case of an EBT-III matrix) is the main tool to operationalize the Gaussian elimination. Anyone who took a linear algebra course can remember the Gaussian elimination, which tries to reduce a matrix to an upper triangular form by operations like

• Multiply first row by 3
• Add second row to the fourth after multiplying it by -2
• …

Each of these operations, which are described by words, can be implemented also by left-multiplication with an elementary matrix. In other words …

We can reduce any matrix to an upper-triangular (or upper-trapezoidal) matrix by left-multiplying with Elementary Matrices of Type I, II, III (p131 of Carl D. Meyer).

And here is the critical part that’s typically not said or not said loud enough: This directly extends to block-matrices. That is, we can reduce any block matrix
$$
G =\begin{pmatrix}
A & B \\ C & D
\end{pmatrix}
$$
to a matrix of the form
$$
W = \begin{pmatrix}
X & Y \\ 0 & Z
\end{pmatrix}
$$
by left-multiplication with an EBT-III matrix E:
$$
E =\begin{pmatrix}
I & 0 \\ L & I
\end{pmatrix}.
$$
That is, $ EG = W$. Critically, $E$ is always nonsingular and extremely easy to invert:
$$
E^{-1} = \begin{pmatrix}
I & 0 \\ -L & I
\end{pmatrix},
$$
which means that $G = E^{-1}W$.
And this is so critical, because once we have a zero block, then computing the rank, inverse, determinant of a matrix etc. become so much simpler. This is particularly easy to trace in the book of David A. Harville, who essentially defines the EBT-III and its main properties in Lemma 8.5.2, which is later used for elaborating on

• The rank of a block matrix (Theorem 8.5.10)
• Generalized inverses of a block matrix (Theorem 9.6.1)
• Positive definiteness of a block matrix in relation to its blocks (Theo rem 14.8.4)

A direct application of an EBT-III matrix is to prove the existence of LU decomposition (for a non-singular matrix with no zeros on pivots). This is shown in Carl D. Meyer (p141-145), but it’s worth to summarize what the EBT-III matrices are doing there. Specifically, Meyer defines an elementary lower-triangular matrix as
$$
T_k = \begin{pmatrix} I & & &\\
0 & 1 & & \\
0 & \mu_k & I &\\
0 & \tilde{\mu}_k & 0 & I
\end{pmatrix},
$$
where $\mu_k$ and $\tilde{\mu}_k$ are appropriately sized vectors, located on the $k$th column of $T_k$. This is clearly an EBT-III matrix. Given any matrix $A$ of size $n\times n$, we can use elementary lower-triangular matrices to achieve the LU decomposition. Specifically, we start with $k=1$ and construct a matrix $T_1$ that, when left-multiplied $A$, eliminates everything below 1st entry of the first column of $A$. Then we proceed with $k=2$ and eliminate all entries below the 2nd entry of the second column of $A$. Continuing in this manner, we form the product
$$
T_{n-1} T_{-2} \dots T_{2} T_{1} A = U.
$$
The resultant $U$ is an upper triangular matrix. Moreover, each of the $T_k$’s is a lower-triangular matrix, therefore the product $T=T_{n-1} T_{-2} \dots T_{2} T_{1}$ is a lower-triangular matrix — another critical property of EBT-III matrices. Finally, since each of the matrices $T_k$ is nonsingular, so is their product $T$, and because the inverse of a lower block-triangular matrix is again lower block-triangular, we have achieve the desired LU decomposition as
$$
A = LU=T^{-1}U.
$$