The nullity theorem

In this section we will prove the nullity theorem in two different ways. Although this theorem is not so widely spread, it can easily be used to derive several interesting results about structured rank matrices and their inverses. It was formulated for the first time by Gustafson [102] for matrices over principal ideal domains. In [73], Fiedler and Markham translated this abstract formulation to matrices over a field. Barrett and Feinsilver formulated theorems close to the nullity theorem in [7,9]. Based on their observations we will provide an alternative proof of this theorem. The theorem will be followed by some small corollaries. In the following section we will apply these corollaries, to classes of matrices closely related to semiseparable matrices.

Definition 6   Suppose a matrix $A\in \mathbb{R}^{m\times n}$ is given. The nullity $\nul(A)$ is defined as the dimension of the right null space of $A$.

Theorem 7 (The nullity theorem)   Suppose we have the following invertible matrix $A\in\mathbb{R}^{n\times n}$ partitioned as

$$A=\left( \begin{array}{cc} A_{11} & A_{12} \\ A_{21} & A_{22} \end{array} \right)$$

with $A_{11}$ of size $p\times q$. The inverse $B$ of $A$ is partitioned as

$$B=\left( \begin{array}{cc} B_{11} & B_{12} \\ B_{21} & B_{22} \end{array} \right)$$

with $B_{11}$ of size $q \times p$. Then the nullities $\nul(A_{11})$ and $\nul(B_{22})$ are equal.

Proof. [ (From [73])] Suppose $\nul(A_{11})\leq \nul(B_{22})$. If this is not true, we can prove the theorem for the matrices

$$\left( \begin{array}{cc} A_{22} & A_... ...left( \begin{array}{cc} B_{22} & B_{21} \\ B_{12} & B_{11} \end{array} \right)$$

which are also each others inverse. Suppose $\nul(B_{22}) > 0$ otherwise $\nul(A_{11})=0$ and the theorem is proved.

When $\nul(B_{22})=c >0$, then there exists a matrix $F$ with $c$ linearly independent columns, such that $B_{22}F=0$. Hence, multiplying the following equation to the right by $F$

$$A_{11}B_{12}+A_{12}B_{22}=0 ,$$

we get

$$A_{11}B_{12}F=0.$$ (1.1)

Applying the same operation to the relation:

$$A_{21}B_{12}+A_{22}B_{22}=I$$

it follows that $A_{21}B_{12}F=F$, and therefore $\rk\left(B_{12}F\right)\geq c$. Using this last statement together with equation (1.1), we derive

$$\nul(A_{11}) \geq \rk\left(B_{12} F\right) \geq c = \nul(B_{12}).$$

Together with our assumption $\nul(A_{11})\leq \nul(B_{22})$, this proves the theorem. $\qedsymbol$

This provides us the first proof of the theorem. The alternative proof is based on some lemmas, and makes use of determinantal formulas. Let us denote with $\vert\alpha\vert$ the cardinality of the corresponding set $\alpha$.

Lemma 8 ([][p. 13)   b101] Suppose $A$ is an $n\times n$ invertible matrix and $\alpha$ and $\beta$ two nonempty sets of indices in $N=\{1,2,\ldots,n\}$, such that $\vert\alpha\vert=\vert\beta\vert<n$. Then, the determinant of any square submatrix of the inverse matrix $B=A^{-1}$ satisfies the following equation

$$\left\vert \det B(\alpha;\beta) \right\vert = \frac{1}{\vert \det (A) \vert} \vert\det A(N\backslash\beta ; N \backslash\alpha) \vert.$$

With $N\backslash\beta$ the difference between the sets $N$ and $\beta$ is meant ($N$ minus $\beta$).

The theorem can be seen as an extension of the standard formula for calculating the inverse of a matrix, for which each element is determined by a minor in the original matrix. This lemma already implies the nullity theorem for square subblocks and for nullities equal to 1, since this case is equivalent with the vanishing of a determinant. The following lemma shows that we can extend this argument also to the general case, i.e. every rank condition can be expressed in terms of the vanishing of certain determinants.

Lemma 9   Suppose $A\in\mathbb{R}^{n\times n}$ is a nonsingular matrix and $n\geq \vert\alpha\vert \geq \vert\beta\vert$. The following three statements are equivalent:

1. $\nul\left(A(\alpha;\beta)\right)\geq d$.
2. $\det A(\alpha' ;\beta') = 0$ for all $\alpha' \subseteq \alpha$ and $\beta' \subseteq \beta$ and $\vert\alpha'\vert=\vert\beta'\vert=\vert\beta\vert-d+1$.
3. $\det A(\alpha' ;\beta') = 0$ for all $\alpha \subseteq \alpha'$ and $\beta \subseteq \beta'$ and $\vert\alpha'\vert=\vert\beta'\vert=\vert\alpha\vert+d-1$.

Proof. The arrows $(1) \Leftrightarrow (2)$ and $(1) \Rightarrow (3)$ are straightforward. The arrow $(3) \Rightarrow (1)$ makes use of the nonsingularity of the matrix $A$. Suppose the nullity of $A(\alpha; \beta)$ to be less than $d$. This would mean that there exist $\vert\beta\vert-d+1$ linearly independent columns in the block $A(\alpha; \beta)$. Therefore $A(\alpha;N)$ has rank less then $\vert\alpha\vert$, implying the singularity of the matrix $A$. $\qedsymbol$

An alternative proof of the nullity theorem can be derived easily combining the previous two lemmas. In [164], Strang proves a related result and comments on different ways to prove the nullity theorem.

The following corollary is a straightforward consequence of the nullity theorem.

Corollary 10 (Corollary 3 in [73])   Suppose $A\in\mathbb{R}^{n\times n}$ is a nonsingular matrix, and $\alpha,\beta$ to be nonempty subsets of $N$ with $\vert\alpha\vert<n$ and $\vert\beta\vert<n$. Then

$$\rk\left(A^{-1}(\alpha ; \beta )\right)=\rk\left(A(N\backslash \beta ; N \backslash \alpha)\right) + \vert\alpha \vert + \vert\beta\vert-n .$$

Proof. By permuting the rows and columns of the matrix $A$, we can always move the submatrix $A(N\backslash \beta; N \backslash \alpha)$ into the upper left part $A_{11}$. Correspondingly, the submatrix $B(\alpha ; \beta )$ of the matrix $B=A^{-1}$ moves into the lower right part $B_{22}$. We have

$$\nul\left(A_{11}\right) = n-\vert\alpha\vert - \rk\left(A_{11}\right)$$

$$\nul\left(B_{22}\right) = \vert\beta\vert -\rk\left(B_{22}\right)$$

and because $\nul\left(A_{11}\right) = \nul\left(B_{22}\right)$, this proves the corollary. $\qedsymbol$

When choosing $\alpha = N\backslash \beta$, we get

Corollary 11   For a nonsingular matrix $A\in\mathbb{R}^{n\times n}$ and $\alpha\subseteq N$, we have:

$$\rk\left(A^{-1}(\alpha ; N \backslash \alpha )\right)=\rk\left(A(\alpha ; N \backslash \alpha)\right) .$$

In the next section we will use the previously obtained results about the ranks of complementary blocks of a matrix and its inverse to prove the rank properties of the inverse for some classes of structured rank matrices.