23. Rank of a matrix

We will retain the notation of the preceding sections. Now let e₁, ··· ,e_n be a base of V. Then the vectors a₁,···,a_m have representations of the form

Obviously, the vector space T is completely fixed by the (m,n)-matrix A=(a_ik). In particular, its dimension r must be determinable from the matrix A - the next task.

Reflections corresponding to those in Section 21, we realize that linear dependence between the vectors a₁,···,a_m is equivalent to linear dependence of the corresponding rows in A, whence Theorem 11 can also have the form:

The dimension r of T equals the maximum number of linearly independent rows in A.

We will now fix the number r in yet another manner in terms of the matrix A. You can form so-called minor determinants in many ways from the (m,n)-matrix A by omission of certain rows and columns until a square, partial matrix is obtained. Consider now all minor determinants of first order in A (that is, all elements of A), then all minor determinants of second order, etc. If l is the smaller of the two numbers m and n (naturally, if m = n, l = m = n), then l is the highest order which a minor determinant of A can have.

It can happen that already all minors of order 1 vanish from A, which is then a null-matrix. If not, all minor determinants of order 2 may vanish, if not, may be, all minor determinants of order three vanish, etc. By examining in this manner all minor determinants of a certain order, you will eventually arrive at a number r when, while there exists in A at least one non-zero minor determinant of order r , all minor determinants of order r+1 vanish or, in the case that r = l, none exist. Here r = 0 shall mean that A is a null-matrix. You now realize immediately: If all minor determinants of order (r+1) vanish, the same result applies to all minor determinants of higher order, for every minor determinant d_r+2 of order r + 2 can be rewritten with the aid of the expansion formulae as a linear combination of minor determinants of order (r+1); if all of the last vanish, then also d_r+2 = 0. Correspondingly, we now conclude that also all minor determinants of order (r + 3) vanish, etc.

The thus determined number r, that is, the largest order among the non-zero minor determinants of A, is called the rank of A. Accordingly, there exists in a matrix of rank r at least one non-zero minor determinant of order r, while all minor determinants of order higher than r, if present, vanish.

Obviously, the rank of a matrix A does not change if you alter arbitrarily the sequence of its rows and columns, for the set of the minor determinants remains the same apart from changes in sign.

Theorem 4 yields

Rank A = Rank A', (23.1)

because the minor determinants, formed from A, have the same values as the ones corresponding to A'.

We will now prove the fundamental

Theorem 12

There exists in a matrix A of Rank r at least one system of r linearly independent rows (columns). Every system of more than r rows (columns) is linearly dependent.

Proof: By (23.1), it is sufficient to prove the rule for rows. Moreover, it is sufficient to prove the second part, namely, that r + 1 rows are linearly dependent, because it then follows that every system of more than r + 1 rows certainly is linearly dependent.

Since the determination of Rank does not depend on the sequence of the rows and columns, you can assume without loss of generality that

(23.2)

We will first of all show that the first r rows of A are linearly independent. In fact, if you set yourself the task of multiplying the first rows consecutively by numbers l₁, ··· l_r, so that you obtain by addition the null-row, you must especially give in the first r locations zeroes. This yields for the numbers l_i the conditions:

a₁₁l₁+ ··· + a_r1l_r = 0,
················································
a_1r l₁+ ··· + a_rr l_r, = 0.

According to the last observation in Section 12, there follows due to (23.3) that l₁ = ··· = l_r = 0, whence the first r rows of A are linearly independent.

Next, we will show that in the case r < m every row of A is linearly dependent on the first r rows. In order to make the following arguments clearer, we will write out the first r rows of A:

a₁₁ ··· a_1r··· a_1p··· a_1n,
················································ (23.3)
a_r1 ··· a_rr··· a_rp··· a_rn,

We shall use anyone row of A:

a_t1 ··· a_tr··· a_tp··· a_tn. (23.4)

We must show that r numbers m₁, ··· , m_r can be determined such that the row (23.4) is obtained, if the rows (23.3) are multiplied consecutively by m₁, ··· , m_r and added. If that can at all be done, then, in particular, there must arise in the first r locations the correct sum, that is,

a₁₁m₁+ ··· + a_r1m_r = a_t1,
················································ (23.4)
a_1rm₁+ ··· + a_rrm_r, = a_tr.

Due to (23.2), Cramer's Rule can be applied to this system of equations, whence there exists exactly one system of r numbers m₁, ··· , m_r which satisfy these equations. If it is at all possible to write the row (23.4) as a linear combination of the rows (23.3), this can only be done with the coefficients m₁, ··· , m_r. However, hitherto, these have been been determined in such a manner that the claimed representability is correct at the first r places. If r = n, the task has been completed; otherwise, you must check whether at the other locations the corresponding element of (23.4) appears as a sum, that is,

a_1pm₁+ ··· + a_rpm_r, = a_tp. (p = r +1, ··· , n). (23.6)

You can confirm that all n - r equations (23.6) are indeed fulfilled in the following manner: The minor determinant of order (r + 1)

has then the value 0, because A has the rank r. In d_1p, multiply the first r rows consecutively by m₁, ··· , m_r and subtract them from the last row. Since d_1p is not changed by this operation, you obtain, taking (23.5) into account,

where c = a_tp - a_1pm₁ - ··· - a_rpm_r. If you expand the last determinant with respect to its last row, you find

Hence, by (23.2), c = 0; this equation says the same as (23.6).

From the fact that all rows of A can be represented as linear sums of the first r rows follows immediately from Theorem 8 that every system with more than r rows depends linearly on A. In fact, all rows of A belong to a vector space of dimension r, for which the first r rows form a base.

Hence Theorem 12 has been proved.

last next