Next: Inverse of structured rank Up: Semiseparable and related matrices, Previous: Definitions for semiseparable and   Contents   Index

# 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 is given. The nullity is defined as the dimension of the right null space of .

Theorem 7 (The nullity theorem)   Suppose we have the following invertible matrix partitioned as

with of size . The inverse of is partitioned as

with of size . Then the nullities and are equal.

Proof. [ (From [73])] Suppose . If this is not true, we can prove the theorem for the matrices

which are also each others inverse. Suppose otherwise and the theorem is proved.

When , then there exists a matrix with linearly independent columns, such that . Hence, multiplying the following equation to the right by

we get

 (1.1)

Applying the same operation to the relation:

it follows that , and therefore . Using this last statement together with equation (1.1), we derive

Together with our assumption , this proves the theorem.

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 the cardinality of the corresponding set .

Lemma 8 ([][p. 13)   b101] Suppose is an invertible matrix and and two nonempty sets of indices in , such that . Then, the determinant of any square submatrix of the inverse matrix satisfies the following equation

With the difference between the sets and is meant ( minus ).

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 is a nonsingular matrix and . The following three statements are equivalent:
1. .
2. for all and and .
3. for all and and .

Proof. The arrows and are straightforward. The arrow makes use of the nonsingularity of the matrix . Suppose the nullity of to be less than . This would mean that there exist linearly independent columns in the block . Therefore has rank less then , implying the singularity of the matrix .

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 is a nonsingular matrix, and to be nonempty subsets of with and . Then

Proof. By permuting the rows and columns of the matrix , we can always move the submatrix into the upper left part . Correspondingly, the submatrix of the matrix moves into the lower right part . We have

and because , this proves the corollary.

When choosing , we get

Corollary 11   For a nonsingular matrix and , we have:

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.

Next: Inverse of structured rank Up: Semiseparable and related matrices, Previous: Definitions for semiseparable and   Contents   Index
Raf Vandebril 2004-05-03