If you are not familiar with how matrices can represent systems of linear equations, start here. If you are not familiar with reduced echelon form, start here. If you are not familiar with the idea that each matrix is uniquely correlated with a specific matrix in reduced echelon form, start here.

Let Ax = b be a system of linear equations. This system is called homogeneous if and only if b=0.

In other words:

Definition 1: Homogeneous System of Linear Equations

Let Ax = b be a system of linear equations. This system of equations is called a homogeneous system of linear equations if and only if b = 0.

The important idea behind homogeneous systems of linear equations is that they always have at least one solution which is called the trivial solution.

For all matrices M, it is clear that if X is a vector of 0's, then MX = 0 where 0 is a vector of 0's. In other words, we are stating M0 = 0.

Definition 2: Trivial Solution of a Homogeneous System of Linear Equations

If MX=0 is a homogeneous system of linear equations, then it is clear that 0 is a solution. Since 0 is a solution to all homogeneous systems of linear equations, this solution is known as the trivial solution.

A nontrivial solution of a homogeneous system of linear equations is any solution to MX=0 where X ≠ 0.

The main conclusion that I will establish in today's blog is that homogeneous system of linear equations will have a nontrivial solution if and only if its determinant is 0.

To establish this point, let's consider some lemmas:

Lemma 1:

Let A be an n x n matrix that represents a homogeneous system of linear equations.

If A has an all-zero column, then there exists a nontrivial solution.

Proof:

(1) Assume that A has an all-zero column at j such that:

A =

so that for all i, a

_{i,j}=0.

(2) Let X =

such that for all i ≠ j, x

_{i,1}=0 and x

_{j,1}= 1 [Note: x

_{j,1}can equal any nonzero value and the argument will still hold]

(3) Let B=AX

(4) For any row i, Row

_{i}(B) = a

_{i,1}*0 + a

_{i,2}*0 + ... + 0*x

_{j,1}+ ... + 0*a

_{i,n}= 0

(5) So, the X defined above is a nontrivial solution.

QED

Definition 3: Free Entry

For any nonzero row, a free entry is any nonzero entry that follows the leading entry, that is, the the free entry and the leading entry are in the same row but the free entry is a column that comes after the leading entry column.

Example 1: Leading Entry

Let A =

A is in reduced echelon form. In this case, row 1 has a leading entry at column 1 and a free entry at column 3. Row 2 has a leading entry at column 2 and a free entry at column 3. Row 3 does not have a leading entry or a free entry.

Lemma 2:

Let A be an n x n matrix in reduced echelon form that represents a homogeneous system of linear equations.

If A has a free entry, then there exists a nontrivial solution.

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

(b) If a column j has a leading entry at row t, then let X

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

(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

= 1*[-(a

(d) For any column j that is a leading entry for another row, a

a

[Note: This is because either a

(e) So, we get that:

Row

(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

(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

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

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

(2) But then we have:

I

(3) By the definition of the I

(4) Thus we have:

0 = I

QED

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 = 0

Proof:

(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

(8) Since A is not invertible, A

(a) Assume that A

(b) Since A is row equivalent A

(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

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

(9) Since A

(a) Assume A

(b) Then A

(c) But A

(10) But if A

(11) And if A

(a) By from the properties of row equivalence, A

(b) Let X be a nontrivial solution for A

A

(c) Then applying step #11a, we have:

A

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

P

(e) So, if X is 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 ≠ 0

Proof:

(1) Assume that det(A)≠0

(2) Then A is invertible. [See Theorem 4, here]

(3) So, we have:

A

(4) Now, A

(5) Likewise A

(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

(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 = 0

Proof:

(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 ≠ 0

Proof:

(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

## 5 comments :

hi,

your blog is quite descriptive but i have a specific question.

how can i find such a non trivial solution to such a homogeneous system?

eg i have x-y=0,x+3y-1=0,5x+3y-2=0.

i keep getting stuck .

hi... i am anusha... i found your blog excellent and it was quite helpful for me to recall my graduate portions...

I have a question based on homogeneous linear system.

a11f11(w)+a12f12(w)...+a1if1i(w)=0

...

...

ai1fi1(w)+ai2fi2(w).....+aiifii(w)=0

i equations, fij is the coefficient, however it is a function of w. How to solve aij? f(w) relations are known.

I used det(fij(w))=0 to get w first, then obtain fij(w) then get aij, which is not very efficient. Any other method?

thank you!

great blog! thanks! :)

nice effort

Post a Comment