Cramer's Rule

In today's blog, I go over the classic result known as Cramer's Rule.

Theorem: Cramer's Rule

Let an n x n matrix A represent a system of linear equations such that AX = B.

Then it follows that if Det(A) ≠ 0, then X has only one unique solution and x_i = det(A_{(Ci ↔ B)})/det(A).

Proof:

(1) Assume that Det(A) ≠ 0

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

(3) Now, A^-1B is a unique solution to AX = B [See Lemma 2, here]

(4) From Corollary 4.1, here, we have:

X = A^-1B = 1/det(A)(adj A)B

(5) Therefore, we have:

x_i = 1/det(A)*∑(j=1,n) ent_i,j(adj A))b_j

[See Definition 1 here for definition of matrix multiplication if needed]

= 1/det(A)*∑(j=1,n) b_j*(cof_j,i(A)) [See Definition 1 here for definition of adj A]

(6) Using Corollary 4.1 here, this gives us:

1/det(A)*∑(j=1,n)b_j*(cof_j,i(A)) = 1/det(A)*det(A_{(Ci ↔ B)}).

(7) Putting it all together gives us:

x_i = 1/det(A)*det(A_{(Ci ↔ B)}).

QED

References

• Charles G. Cullen, Matrices and Linear Transformations, Dover Publications, Inc., 1972.
• "Cramer's Rule", PlanetMath.org
  

Homogeneous System of Linear Equations

In today's blog, I talk about homogeneous systems of linear equations. In essence, this extends a previous blog on systems of linear equations and their representation through matrices.

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_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₁ + ... + 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₁ + ... + 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_nX = 0

(3) By the definition of the I_n (See Definition 1, here), we know that I_nX = X

(4) Thus we have:

0 = I_nX = X

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

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

A_rX = PAX = 0

(d) Now P is invertible (see step #8c above), so we can multiply P^-1 to both sides to get:

P^-1PAX = AX = P^-10=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^-1AX = A^-10

(4) Now, A^-1AX = I_nX = X [See Definition 1, here]

(5) Likewise A^-10 = 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