# 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 **E**lementary **B**lock-matrix of **T**ype-**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.

$$