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.
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
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
20040503