English | Español

Try our Free Online Math Solver!

Online Math Solver












Please use this form if you would like
to have this math solver on your website,
free of charge.

Algebra of Matrices Systems of Linear Equations

5. Systems of linear equations II: Rouché-Capelli's theorem and
Cramer's theorem

Rouché-Capelli's theorem provides a useful tool to determine whether a system is
solvable or not .

Theorem 4 (Rouché-Capelli). Let AX = b be . Such LS is
solvable if and only if rank (A) = rank (A b).
If such system is solvable, then it admits solutions.

Proof. AX = b is solvable there exists such that Aa = b
there exists such that

rank (A b).
Now, suppose that the LS(m, n,R) AX = b is solvable and denote r = rank (A) =
rank (A b). Without any loss of generality (up to interchanging the rows of A), we
can assume that the first r rows of A are linearly independent . Therefore, also the
first r rows of (A b) are linearly independent (and the remaining m−r are a linear
combinations of the former ).

Let us denote:

and consider the LS(r, n,R) A * X = b* . It is easy to see that this LS is equivalent
to the original one; hence, we will solve A *X = b* , instead of AX = b.
If we apply the Gauss-Jordan algorithm to A *X = b* , since this system is compatible,
we will end up with a step LS ; moreover, since rank (A) = r and the rank is
preserved by elementary operations, we won't obtain any zero row! In the end our
step system will have exactly r equations and , as observed in prop. 6, it will have

Proposition 9.
Let and . One has:

rank (AB) ≤ min{rank (A), rank (B)}.

Proof. It is sufficient to verify that rank (AB) ≤rank (B). In fact, if this inequality
is true, it follows that:

Let us consider the i-th row of AB:

Therefore, . It follows that

and consequently rank (AB) ≤ rank (B).

Corollary 2.
Let . For any and , one

rank (A) = rank (AB) = rank (CA).

Proof. We have: rank (AB) ≤ rank (A) = rank (ABB -1) ≤ rank (AB); therefore,

rank (AB) = rank (A) .

Analogously: rank (CA) ≤ rank (A) = rank (C-1CA) ≤ rank (CA); therefore,

rank (CA) = rank (A) .

Let us state and prove another method , that can be used to solve LS(n, n,R):
Cramer's method.

Theorem 5. Let AX = b a LS(n, n,R), with . We have:

i) this LS has a unique solution;
ii) for i = 1, . . . , n let us denote with the matrix obtained by A, substituting
the i-th column with b. The unique solution of this LS is given by:

(Cramer' s formula ).

Proof. i) The column x = A-1b is a solution of AX = b; in fact:

If y is another solution, then:

therefore, the solution is unique.

ii) Let us compute the determinant of , using Laplace's expansion (cofactors
expansion) with respect to the i-th column:

[in fact, the cofactors w.r.t. the i-th column of A and B coincide].
Since , then

and consequently (for i = 1, . . . , n):

From Rouché-Capelli's theorem, it follows that, in order to decide whether a LS
AX = b is solvable or not, one has to compute ( and then compare ) rank (A) and
rank (A b).

To compute the rank of a matrix, the following result (Kroenecker's theorem or
theorem of the bordered minors) will come in handy, saving a lot of computations!
Let us start with a Definition.

Let B be a square submatrix of order r, of a matrix .
We will call a bordered minor of B, the determinant of any square submatrix C of
A, of order r + 1 and such that it contains B as a submatrix. We will say that C
is obtained by bordering B with a row and a column of A.
Obviously, if r = min{m, n} B has no bordered minors.

Theorem 6 (Kroenecker).
Let . We have that rank (A) = r if and
only if the two following conditions are satisfied:

a) there exists in A an invertible square submatrix B of order r;
b) all bordered minors of B (if there exist any) are zero.

Proof. (=>) If rank (A) = r, then (A) = r and therefore there exists an invertible
submatrix of A of order r: . Moreover, all minors of order
r + 1 of A (and in particular the bordered minors of B) are zero. Hence,
conditions a) and b) are satisfied.

() To simplify the notation, let us suppose that B = A(1, . . . , r | 1, . . . , r). By
hypothesis, det(B) ≠ 0 (i.e., rank (B) = r).
Let C = () be the submatrix of A, formed by the first r columns
of A. Obviously, rank (C) ≤r; since B is a submatrix of C, then r =
rank (B) ≤rank (C) ≤ r and consequently, rank (C) = r. Hence, the
columns are linearly independent.

To show the claim (i.e., rank (A) = r), we need to prove that:

namely, that for t = r + 1, . . . , n, the matrix has rank
Let us denote such matrix by and consider the submatrix
formed by the first r rows:

This submatrix has rank r (it has B as a submatrix, therefore it must have
maximal rank). To prove the claim (i.e., rank (D) = r), it suffices to verify:

In fact, for s = r + 1, . . . ,m, consider . This is a bordered

matrix of B, therefore it is zero. This means that its first r + 1 columns
are linearly dependent and, since the first r are linearly independent,
we have necessarily:

as we wanted to show.

Remark. Let . To compute the rank one can proceed as follows:

• find in A an invertible square matrix B of order t;
• if t = min{m, n}, then rank (A) = t;
• if t < min{m, n}, consider all possible bordered minors of B;
• if all bordered minors of B are zero, then rank (A) = t;
• otherwise, we have obtained a new invertible square matrix C of order t+1;
• therefore, rank (A) ≥t + 1 and we repeat the above procedure.

Without Kroenecker's theorem, once we have found an invertible square submatrix
B of order t, we should check that all possible minors of order t + 1 are zero; they
are ; while the bordered minors of B are only (m − t)(n − t).
For instance, if and , the minors of A of order 3 are
, while the bordered minors are (4 − 2)(6 − 2) = 8.

Remark. Let AX = b be a given LS(m, n,R). Let M = (A b) be its complete
matrix and let r = rank (A). From Rouché-Capelli's theorem, such LS is solvable
if and only if rank (A b) = r. In this case, it has solutions.

We want to describe now a procedure to find such solutions (without using Gauss-
Jordan's method).

Choose in A an invertible square submatrix B of order r (that we will call fun-
damental submatrix of the LS). For instance, let .

and consider the new LS(r, n,R): A'X = b'. This system is equivalent to the original
one, since it has been obtained by eliminating m− r equations, corresponding
to the rows of A that could be expressed as linear combinations of the remaining r.
Let us solve this new system. Bring the n− r unknowns different from
to the right-hand side and attribute to them the values (arbitrarily
chosen). We get in this way, a system LS(r, r,R) that admits a unique solution
(since the coefficient matrix B is invertible), that can be expressed by Cramer's
formula. Varying the n − r parameters , we get the set of the
solutions of the LS.

A particular simple solution of the system, is obtained by choosing
; let us denote it by . Using prop. 5, (where denotes
the vector space of the solutions of A'X = 0); therefore, instead of computing the
generic solution of , it might be more convenient to compute the generic solution
of this HLS and then sum it up to .

Attributing to the values,

(1, 0, . . . , 0), (0, 1, 0, . . . , 0), . . . , (0, . . . , 0, 1) ,

we get n − r systems LS(r, r,R), each of which admits a unique solution. These
n−r solutions are linearly independent and hence form a basis of .

Remark. We have already observed that a HLS AX = 0 is always solvable (in
fact, it has at least the trivial solution). This fact, is con rmed by Rouché-Capelli's
theorem; in fact, rank (A) is clearly equal to rank (A 0). From the same theorem,
it follows that every HLS(m, n,R) AX = 0 has .
One can verify that a HLS has no eigensolutions (i.e., the only solution is the
trivial one), if and only if n = rank (A) [in fact, ].

Prev Next