.

.

column.

. In this case,

.

.

.

Proof:

(1) We can assume that

A does not have any zero columns. If it did, then it would have a

nontrivial solution by Lemma 1 above.

(2) By definition of

reduced echelon form (see Definition 2,

here), each column is either a leading entry for a row (one row has a 1 at this column and all other rows have a 0) or a free entry for a row (the column is never a leading entry for any row).

(3) We can now build a vector

X in the following way:

(a) If a column

j is a

free entry (that is, it has at least one free entry in its column), then let

X_{j,1}** = 1**.

(b) If a column

j has a

leading entry at row

t, then let

X_{j,1} = -(a_{t,j+1} + ... + a_{t,n})NOTE: By the definition of reduced echelon form, if any row of a column is a leading entry, then all other rows of that column are 0.

(4) Let

B = AX.

(5) Then, for any nonzero row

i in

B:

(a) Let

li(i) be the column which is the leading index for row

i.

(b)

Row_{i}(B) = a_{i,1}*x_{1} + ... + a_{i,li(i)}*[-(a_{i,li(i)+1} + ... + a_{i,n})] + ... + a_{i,n}*x_{n}(c) Now, for row

i, we know that all columns before

li(i) are zero and the entry at

li(i)=1, so we have:

Row_{i}(B) = 0*x_{1} + ... + a_{i,li(i)}*[-(a_{i,li(i)+1} + ... + a_{i,n})] + ... + a_{i,n}*x_{n} == 1*[-(a_{i,li(i)+1} + ... + a_{i,n})] + ... + a_{i,n}*x_{n}(d) For any column

j that is a leading entry for another row,

a_{i,j}=0 (from the definition of reduced echelon form), so we know that the sum for all columns after

li(i) are:

a_{i,li(i)+1} + ... + a_{i,n}[Note: This is because either

a_{i,j}=0 or

x_{j}=1 when

a_{i,j} is nonzero]

(e) So, we get that:

Row_{i}(B) = -(a_{i,li(i)+1} + ... + a_{i,n}) + (a_{i,li(i)+1} + ... + a_{i,n}) = 0(6) We know that

X is not the trivial solution since, by assumption, we assumed that

A has a free entry. It therefore follows that

X ≠ 0 [since if

j is the column with the free entry, then

x_{j}=1]

(7) Therefore, it follows that

A has a

nontrivial solution.

QED

Lemma 3:If an

n x n matrix

A is in

reduced echelon form and

A has

n nonzero rows, then

A = I_{n}.

Proof:

(1) If

A has

n nonzero rows, then each row has a leading entry.

(2) This means that all

n columns must have a leading entry so that for each row, there is only nonzero entry, the leading entry which is

1.

(3) But, we also know that the first row must have a leading entry in the column before the leading entry of the second row and so on.

(4) The only way that this can occur is if the leading for row 1 is in column 1 and the leading entry for row 2 is in column 2 and so on since this is the only way to order the

n columns which make up the

n leading entries.

(5) Thus,

A must equal

I_{n} (see Definition 1,

here for definition of the

Identity Matrix).

QED

Lemma 4:Let

A be an

n x n matrix in

reduced echelon form that represents a

homogeneous system of linear equations.

If

A has

n nonzero rows, then there is only one solution: the

trivial solution.

Proof:

(1) If

A has

n nonzero rows and

A is in

reduced echelon form, then by Lemma 3 above,

A = I_{n}.

(2) But then we have:

I_{n}X = 0(3) By the definition of the

I_{n} (See Definition 1,

here), we know that

I_{n}X = X(4) Thus we have:

0 = I_{n}X = XQED

Lemma 5:If an

n x n matrix

A is in

reduced echelon form and

A has a zero row, then

A has a

nontrivial solution.

Proof:

(1) If

A has a zero row, then then there are at most

n-1 columns with leading entries and one column cannot have a leading entry since:

(a) Assume that all columns have a leading entry.

(b) Then there are necessarily

n leading entries

(c) But then since each leading entry must be on its own row, there must be

n nonzero rows.

(d) But this is impossible since there is at least one zero row so we have a contradiction and we reject our assumption in (a).

(2) But if a column does not have a leading entry, then it is necessarily an all-zero column or it contains free entries.

(3) If it is an all zero column, the

A has a

nontrivial solution by Lemma 1 above. If it contains free entries, then

A has a nontrivial solution by Lemma 2 above. Either way,

A has a nontrivial solution.

QED

Theorem 6:An

n x n matrix that represents a

homogeneous system of linear equations has a

nontrivial solution if and only if its

determinant = 0Proof:

(1) Assume that a matrix has a

nontrivial solution.

(2) Assume that its

determinant ≠ 0(3) By Cramer's Rule (see Theorem,

here), if

determinant ≠ 0, then the matrix has a unique solution. But if matrix has a unique solution, then it does not have a

nontrivial solution (since we know that the trivial solution must be this unique solution).

(4) Therefore we have a contradiction and we reject our assumption at step #2 and conclude that

determinant = 0.

(5) Assume that

det(A) = 0(6) Then it follows that

A is not

invertible. [See Theorem 4,

here]

(7) Since every matrix has a

reduced echelon form (see Theorem 1,

here), let

A_{r} be the reduced echelon form for

A.

(8) Since

A is not invertible,

A_{r} cannot be invertible since:

(a) Assume that

A_{r} is invertible.

(b) Since

A is row equivalent

A_{r}, there exists a matrix

P that is a product of elementary matrices such that

A = PA_{r} [See Theorem 5, see

here]

(c) Since each of the elementary matrices are invertible [see Lemma 4,

here] and P is the product of elementary matrices,

P is invertible. [See Corollary 3.1,

here]

(d) Since

P is invertible and

A_{r} is invertible by assumption, it follows that

A must be invertible [See Corollary 3.1,

here]

(e) But

A is not invertible so we have a contradiction and we reject our assumption in step #8a.

(9) Since

A_{r} is not invertible, it is not equal to

I_{n} (since

I_{n} is invertible to itself), and

A_{r} must have a zero row since:

(a) Assume

A_{r} did not have a zero row.

(b) Then

A_{r} = I_{n} [See Lemma 3, above]

(c) But

A_{r} ≠ I_{n} so we have a contradiction and we reject our assumption at step #9a.

(10) But if

A_{r} has a nonzero row, then

A_{r} has a nontrivial solution. [See Lemma 5 above]

(11) And if

A_{r} has a nontrivial solution, then

A has a nontrivial solution since:

(a) By from the properties of row equivalence,

A_{r} = PA [See Theorem 5,

here]

(b) Let

X be a nontrivial solution for

A_{r} such that:

A_{r}X = 0(c) Then applying step #11a, we have:

A_{r}X = PAX = 0(d) Now

P is invertible (see step #8c above), so we can multiply

P^{-1} to both sides to get:

P^{-1}PAX = AX = P^{-1}0=0(e) So, if

X is a nontrivial solution for

A_{r}, it is also necessarily a nontrivial solution for

A.

QED

Corollary 6.1:An

n x n matrix that represents a

homogeneous system of linear equations has only the

trivial solution if and only if its

determinant ≠ 0Proof:

(1) Assume that

det(A)≠0(2) Then

A is

invertible. [See Theorem 4,

here]

(3) So, we have:

A^{-1}AX = A^{-1}0(4) Now,

A^{-1}AX = I_{n}X = X [See Definition 1,

here]

(5) Likewise

A^{-1}0 = 0(6) So,

X = 0(7) Assume that the only solution is the

trivial solution.

(8) Assume that

Det(A) = 0(9) But by Theorem 6 above,

AX=0 must have a nontrivial solution.

(10) But this is a contradiction so we reject our assumption in step #8.

(11) Therefore

Det(A) ≠ 0 QED