The rank–nullity theorem is a theorem in
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrice ...
, which asserts that the
dimension
In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coord ...
of the
domain
Domain may refer to:
Mathematics
*Domain of a function, the set of input values for which the (total) function is defined
** Domain of definition of a partial function
** Natural domain of a partial function
**Domain of holomorphy of a function
* ...
of a
linear map
In mathematics, and more specifically in linear algebra, a linear map (also called a linear mapping, linear transformation, vector space homomorphism, or in some contexts linear function) is a mapping V \to W between two vector spaces that ...
is the sum of its
rank
Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as:
Level or position in a hierarchical organization
* Academic rank
* Diplomatic rank
* Hierarchy
* ...
(the dimension of its
image
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensio ...
) and its ''nullity'' (the dimension of its
kernel).
[ p. 70, §2.1, Theorem 2.3]
Stating the theorem
Let
be a linear transformation between two vector spaces where
's domain
is finite dimensional. Then
where
In other words,
This theorem can be refined via the
splitting lemma to be a statement about an
isomorphism
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word i ...
of spaces, not just dimensions. Explicitly, since induces an isomorphism from
to
the existence of a basis for that extends any given basis of
implies, via the splitting lemma, that
Taking dimensions, the rank–nullity theorem follows.
Matrices
Since
one can represent linear maps as
matrices
Matrix most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** ''The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
. In the case of an
matrix, the dimension of the domain is
the number of columns in the matrix. Thus the rank–nullity theorem for a given matrix
immediately becomes
Proofs
Here we provide two proofs. The first
operates in the general case, using linear maps. The second proof looks at the homogeneous system
for
with
rank
Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as:
Level or position in a hierarchical organization
* Academic rank
* Diplomatic rank
* Hierarchy
* ...
and shows explicitly that there exists a set of
linearly independent solutions that span the kernel of
.
While the theorem requires that the domain of the linear map be finite-dimensional, there is no such assumption on the codomain. This means that there are linear maps not given by matrices for which the theorem applies. Despite this, the first proof is not actually more general than the second: since the image of the linear map is finite-dimensional, we can represent the map from its domain to its image by a matrix, prove the theorem for that matrix, then compose with the inclusion of the image into the full codomain.
First proof
Let
be vector spaces over some field
and
defined as in the statement of the theorem with
.
As
is a
subspace, there exists a basis for it. Suppose
and let
be such a basis.
We may now, by the
Steinitz exchange lemma, extend
with
linearly independent vectors
to form a full basis of
.
Let
such that
is a basis for
.
From this, we know that
We now claim that
is a basis for
.
The above equality already states that
is a generating set for
; it remains to be shown that it is also linearly independent to conclude that it is a basis.
Suppose
is not linearly independent, and let
for some
.
Thus, owing to the linearity of
, it follows that
This is a contradiction to
being a basis, unless all
are equal to zero. This shows that
is linearly independent, and more specifically that it is a basis for
.
To summarize, we have
, a basis for
, and
, a basis for
.
Finally we may state that
This concludes our proof.
Second proof
Let
with
linearly independent columns (i.e.
). We will show that:
To do this, we will produce a matrix
whose columns form a
basis of the null space of
.
Without loss of generality, assume that the first
columns of
are linearly independent. So, we can write
where
*
with
linearly independent column vectors, and
*
, each of whose
columns are linear combinations of the columns of
.
This means that
for some
(see
rank factorization In mathematics, given a field \mathbb F, nonnegative integers m,n, and a matrix A\in\mathbb F^, a rank decomposition or rank factorization of is a factorization of of the form , where C\in\mathbb F^ and F\in\mathbb F^, where r=\operatorname A is ...
) and, hence,
Let
where
is the
identity matrix
In linear algebra, the identity matrix of size n is the n\times n square matrix with ones on the main diagonal and zeros elsewhere.
Terminology and notation
The identity matrix is often denoted by I_n, or simply by I if the size is immaterial or ...
. We note that
satisfies
Therefore, each of the
columns of
are particular solutions of
.
Furthermore, the
columns of
are
linearly independent because
will imply
for
:
Therefore, the column vectors of
constitute a set of
linearly independent solutions for
.
We next prove that ''any'' solution of
must be a
linear combination of the columns of
.
For this, let
be any vector such that
. Note that since the columns of
are linearly independent,
implies
.
Therefore,
This proves that any vector
that is a solution of
must be a linear combination of the
special solutions given by the columns of
. And we have already seen that the columns of
are linearly independent. Hence, the columns of
constitute a basis for the
null space
In mathematics, the kernel of a linear map, also known as the null space or nullspace, is the linear subspace of the domain of the map which is mapped to the zero vector. That is, given a linear map between two vector spaces and , the kern ...
of
. Therefore, the
nullity of
is
. Since
equals rank of
, it follows that
. This concludes our proof.
Reformulations and generalizations
This theorem is a statement of the
first isomorphism theorem of algebra for the case of vector spaces; it generalizes to the
splitting lemma.
In more modern language, the theorem can also be phrased as saying that each short exact sequence of vector spaces splits. Explicitly, given that
is a
short exact sequence of vector spaces, then
, hence
Here ''R'' plays the role of im ''T'' and ''U'' is ker ''T'', i.e.
In the finite-dimensional case, this formulation is susceptible to a generalization: if
is an
exact sequence
An exact sequence is a sequence of morphisms between objects (for example, groups, rings, modules, and, more generally, objects of an abelian category) such that the image of one morphism equals the kernel of the next.
Definition
In the context ...
of finite-dimensional vector spaces, then
The rank–nullity theorem for finite-dimensional vector spaces may also be formulated in terms of the ''index'' of a linear map. The index of a linear map
, where
and
are finite-dimensional, is defined by
Intuitively,
is the number of independent solutions
of the equation
, and
is the number of independent restrictions that have to be put on
to make
solvable. The rank–nullity theorem for finite-dimensional vector spaces is equivalent to the statement
We see that we can easily read off the index of the linear map
from the involved spaces, without any need to analyze
in detail. This effect also occurs in a much deeper result: the
Atiyah–Singer index theorem
In differential geometry, the Atiyah–Singer index theorem, proved by Michael Atiyah and Isadore Singer (1963), states that for an elliptic differential operator on a compact manifold, the analytical index (related to the dimension of the sp ...
states that the index of certain differential operators can be read off the geometry of the involved spaces.
Citations
References
*
*
*
*.
*
*
{{DEFAULTSORT:Rank-nullity theorem
Theorems in linear algebra
Isomorphism theorems
Articles containing proofs