Notes on Linear Algebra

Definition 1.1.1 (Matrix) A rectangular array of numbers is called a matrix.

The horizontal arrays of a matrix are called its rows and the vertical arrays are called its columns. A matrix is said to have the order m × n if it has m rows and n columns. An m × n matrix A can be represented in either of the following forms:

⌊a11 a12 ⋅⋅⋅ a1n⌋ ( a11 a12 ⋅⋅⋅ a1n) |a21 a22 ⋅⋅⋅ a2n| | a21 a22 ⋅⋅⋅ a2n| A = || . . . . || or A = || . . . . || , ⌈ .. .. .. .. ⌉ ( .. .. .. .. ) am1 am2 ⋅⋅⋅ amn am1 am2 ⋅⋅⋅ amn

where a_ij is the entry at the intersection of the i^th row and j^th column. In a more concise manner, we also write A_m×n = [a_ij] or A = [a_ij]_m×n or A = [a_ij]. We shall mostly be concerned with matrices having real numbers, denoted ℝ, as entries. For example, if A = [ ]
1 3 7
4 5 6

then a₁₁ = 1, a₁₂ = 3,a₁₃ = 7,a₂₁ = 4,a₂₂ = 5, and a₂₃ = 6.

A matrix having only one column is called a column vector; and a matrix with only one row is called a row vector. Whenever a vector is used, it should be understood from the context whether it is a row vector or a column vector. Also, all the vectors will be represented by bold letters.

Definition 1.1.2 (Equality of two Matrices) Two matrices A = [a_ij] and B = [b_ij] having the same order m × n are equal if a_ij = b_ij for each i = 1,2,…,m and j = 1,2,…,n.

In other words, two matrices are said to be equal if they have the same order and their corresponding entries are equal.

Example 1.1.3 The linear system of equations 2x + 3y = 5 and 3x + 2y = 5 can be identified with the matrix [ ]
2 3 : 5
3 2 : 5 . Note that x and y are indeterminate and we can think of x being associated with the first column and y being associated with the second column.

1.1.1 Special Matrices

Definition 1.1.4

A matrix in which each entry is zero is called a zero-matrix, denoted by 0. For example, $[0 0] [0 0 0] 02×2 = 0 0 and 02×3 = 0 0 0 .$
A matrix that has the same number of rows as the number of columns, is called a square matrix. A square matrix is said to have order n if it is an n × n matrix.
The entries a₁₁,a₂₂,…,a_nn of an n×n square matrix A = [a_ij] are called the diagonal entries (the principal diagonal) of A.
A square matrix A = [a_ij] is said to be a diagonal matrix if a_ij = 0 for i≠j. In other words, the non-zero entries appear only on the principal diagonal. For example, the zero matrix 0_n and are a few diagonal matrices.
A diagonal matrix D of order n with the diagonal entries d₁,d₂,…,d_n is denoted by D = diag(d₁,…,d_n). If d_i = d for all i = 1,2,…,n then the diagonal matrix D is called a scalar matrix.
A scalar matrix A of order n is called an identity matrix if d = 1. This matrix is denoted by I_n.
For example, I₂ = and I₃ = . The subscript n is suppressed in case the order is clear from the context or if no confusion arises.
A square matrix A = [a_ij] is said to be an upper triangular matrix if a_ij = 0 for i > j.
A square matrix A = [a_ij] is said to be a lower triangular matrix if a_ij = 0 for i < j.
A square matrix A is said to be triangular if it is an upper or a lower triangular matrix.

For example, ⌊ ⌋
0 1 4
⌈0 3 - 1⌉
0 0 - 2 is upper triangular, ⌊ ⌋
0 0 0
⌈1 0 0⌉
0 1 1 is lower triangular.

Exercise 1.1.5 Are the following matrices upper triangular, lower triangular or both?

The square matrices 0 and I or order n.
The matrix diag(1,-1,0,1).

1.2 Operations on Matrices

Definition 1.2.1 (Transpose of a Matrix) The transpose of an m × n matrix A = [a_ij] is defined as the n × m matrix B = [b_ij], with b_ij = a_ji for 1 ≤ i ≤ m and 1 ≤ j ≤ n. The transpose of A is denoted by A^t.

That is, if A = [ ]
1 4 5
0 1 2 then A^t = ⌊1 0⌋
⌈4 1⌉
5 2 . Thus, the transpose of a row vector is a column vector and vice-versa.

Theorem 1.2.2 For any matrix A, (A^t)^t = A.

Proof. Let A = [a_ij],A^t = [b_ij] and (A^t)^t = [c_ij]. Then, the definition of transpose gives

cij = bji = aij for all i,j

and the result follows. □

Definition 1.2.3 (Addition of Matrices) let A = [a_ij] and B = [b_ij] be two m × n matrices. Then the sum A + B is defined to be the matrix C = [c_ij] with c_ij = a_ij + b_ij.

Note that, we define the sum of two matrices only when the order of the two matrices are same.

Definition 1.2.4 (Multiplying a Scalar to a Matrix) Let A = [a_ij] be an m × n matrix. Then for any element k ∈ ℝ, we define kA = [ka_ij].

For example, if A = [1 4 5]
0 1 2 and k = 5, then 5A = [5 20 25]
0 5 10 .

Theorem 1.2.5 Let A,B and C be matrices of order m × n, and let k,ℓ ∈ ℝ. Then

A + B = B + A (commutativity).
(A + B) + C = A + (B + C) (associativity).
k(ℓA) = (kℓ)A.
(k + ℓ)A = kA + ℓA.

Proof. Part 1.
Let A = [a_ij] and B = [b_ij]. Then

A + B = [aij]+ [bij] = [aij + bij] = [bij + aij] = [bij]+ [aij] = B + A

as real numbers commute.

The reader is required to prove the other parts as all the results follow from the properties of real numbers. □

Definition 1.2.6 (Additive Inverse) Let A be an m × n matrix.

Then there exists a matrix B with A + B = 0. This matrix B is called the additive inverse of A, and is denoted by -A = (-1)A.
Also, for the matrix 0_m×n, A+0 = 0+A = A. Hence, the matrix 0_m×n is called the additive identity.

Exercise 1.2.7

Find a 3 × 3 non-zero matrix A satisfying A = A^t.
Find a 3 × 3 non-zero matrix A such that A^t = -A.
Find the 3 × 3 matrix A = [a_ij] satisfying a_ij = 1 if i≠j and 2 otherwise.
Find the 3 × 3 matrix A = [a_ij] satisfying a_ij = 1 if |i - j|≤ 1 and 0 otherwise.
Find the 4 × 4 matrix A = [a_ij] satisfying a_ij = i + j.
Find the 4 × 4 matrix A = [a_ij] satisfying a_ij = 2^i+j.
Suppose A + B = A. Then show that B = 0.
Suppose A + B = 0. Then show that B = (-1)A = [-a_ij].
Let A = and B = . Compute A + B^t and B + A^t.

1.2.1 Multiplication of Matrices

Definition 1.2.8 (Matrix Multiplication / Product) Let A = [a_ij] be an m×n matrix and B = [b_ij ] be an n × r matrix. The product AB is a matrix C = [c_ij] of order m × r, with

n∑ cij = aikbkj = ai1b1j + ai2b2j + ⋅⋅⋅+ ainbnj. k=1

That is, if A_m×n = ⌊ ⌋
⋅⋅⋅ ⋅⋅⋅ ⋅⋅⋅ ⋅⋅⋅
|| ⋅⋅⋅ ⋅⋅⋅ ⋅⋅⋅ ⋅⋅⋅ ||
|| a a ⋅⋅⋅ a ||
|⌈ i1 i2 in |⌉
⋅⋅⋅ ⋅⋅⋅ ⋅⋅⋅ ⋅⋅⋅
⋅⋅⋅ ⋅⋅⋅ ⋅⋅⋅ ⋅⋅⋅ and B_n×r = ⌊ ⌋
... b1j ...
|| . .||
|| .. b2j ..||
|| ... ... ...||
⌈ . .⌉
.. bmj .. then

AB = [(AB )ij]m×r and (AB )ij = ai1b1j + ai2b2j + ⋅⋅⋅+ ainbnj.

Observe that the product AB is defined if and only if
the number of columns of A = the number of rows of B.

For example, if A = [ ]
a b c
d e f and B = ⌊ α β γ δ⌋
⌈ x y z t⌉
u v w s then

[ ] AB = aα+ bx +cu aβ + by+ cv aγ + bz + cw aδ + bt + cs . dα + ex+ fu dβ + ey+ fv dγ + ez + fw dδ +et+ f s

(1.2.1)

Observe that in Equation (1.2.1), the first row of AB can be re-written as

[ ] [ ] [ ] a ⋅α β γ δ + b⋅ x y z t + c⋅ u v w s .

That is, if Row_i(B) denotes the i-th row of B for 1 ≤ i ≤ 3, then the matrix product AB can be re-written as

[ ] a ⋅ Row1 (B)+ b⋅ Row2 (B )+ c⋅ Row3(B ) AB = d ⋅ Row1 (B )+ e⋅ Row2(B )+ f ⋅ Row3(B ) . (1.2.2)

Similarly, observe that if Col_j(A) denotes the j-th column of A for 1 ≤ j ≤ 3, then the matrix product AB can be re-written as

[ AB = Col1(A )⋅α +Col2(A) ⋅x + Col3(A )⋅u, Col (A)⋅β + Col (A )⋅y+ Col (A)⋅v, 1 2 3 Col1(A)⋅γ + Col2(A )⋅z + Col3(A)⋅w Col1(A )⋅δ+ Col2(A )⋅t+ Col3(A )⋅s]. (1.2.3)

Remark 1.2.9 Observe the following:

In this example, while AB is defined, the product BA is not defined.
However, for square matrices A and B of the same order, both the product AB and BA are defined.
The product AB corresponds to operating on the rows of the matrix B (see Equation (1.2.2)). This is row method for calculating the matrix product.
The product AB also corresponds to operating on the columns of the matrix A (see Equation (1.2.3)). This is column method for calculating the matrix product.
Let A = [a_ij] and B = [b_ij] be two matrices. Suppose _1,_2,…,_n are the rows of A and b₁,b₂,…,b_p are the columns of B. If the product AB is defined, then check that
$⌊ ⌋ a1B ||a2B || AB = [Ab1,Ab2, ...,Abp ] = |⌈ .. |⌉. . anB$

Example 1.2.10 Let A = ⌊ ⌋
1 2 0
⌈ 1 0 1⌉
0 - 1 1 and B = ⌊ ⌋
1 0 - 1
⌈0 0 1 ⌉
0 - 1 1 . Use the row/column method of matrix multiplication to

find the second row of the matrix AB.
Solution: Observe that the second row of AB is obtained by multiplying the second row of A with B. Hence, the second row of AB is $1⋅[1,0,- 1]+ 0 ⋅[0,0,1]+ 1⋅[0,- 1,1] = [1,- 1,0].$
find the third column of the matrix AB.
Solution: Observe that the third column of AB is obtained by multiplying A with the third column of B. Hence, the third column of AB is $⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌈1⌉ ⌈ 2 ⌉ ⌈0⌉ ⌈1⌉ - 1⋅ 1 + 1⋅ 0 + 1⋅ 1 = 0 . 0 - 1 1 0$

Definition 1.2.11 (Commutativity of Matrix Product) Two square matrices A and B are said to commute if AB = BA.

Remark 1.2.12 Note that if A is a square matrix of order n and if B is a scalar matrix of order n then AB = BA. In general, the matrix product is not commutative. For example, consider A = [11]
00 and B = [1 0]
1 0 . Then check that the matrix product

[2 0] [1 1] AB = ⁄= = BA. 0 0 1 1

Theorem 1.2.13 Suppose that the matrices A,B and C are so chosen that the matrix multiplications are defined.

Then (AB)C = A(BC). That is, the matrix multiplication is associative.
For any k ∈ ℝ,(kA)B = k(AB) = A(kB).
Then A(B + C) = AB + AC. That is, multiplication distributes over addition.
If A is an n × n matrix then AI_n = I_nA = A.
For any square matrix A of order n and D = diag(d₁,d₂,…,d_n), we have
- the first row of DA is d₁ times the first row of A;
- for 1 ≤ i ≤ n, the i^th row of DA is d_i times the i^th row of A.
A similar statement holds for the columns of A when A is multiplied on the right by D.

Proof. Part 1. Let A = [a_ij]_m×n,B = [b_ij]_n×p and C = [c_ij]_p×q. Then

p n (BC ) = ∑ b c and (AB ) = ∑ a b . kj ℓ=1 kℓ ℓj iℓ k=1 ikkℓ

Therefore,

∑n ∑n ∑p (A (BC ))ij = aik(BC )kj = aik( bkℓcℓj) k=1 p k=1 ℓ=p1 ∑n ∑ ∑n ∑ = aik(bkℓcℓj) = (aikbkℓ)cℓj k=p1ℓ=n1 k=t1ℓ=1 = ∑ (∑ a b )c = ∑ (AB ) c ℓ=1 k=1 ik kℓ ℓj ℓ=1 iℓ ℓj = ((AB )C)ij.

Part 5. For all j = 1,2,…,n, we have

∑n (DA )ij = dikakj = diaij k=1

as d_ik = 0 whenever i≠k. Hence, the required result follows.

The reader is required to prove the other parts. □

Exercise 1.2.14

Find a 2 × 2 non-zero matrix A satisfying A² = 0.
Find a 2 × 2 non-zero matrix A satisfying A² = A and A≠I₂.
Find 2 × 2 non-zero matrices A,B and C satisfying AB = AC but B≠C. That is, the cancelation law doesn’t hold.
Let A = . Compute A + 3A² - A³ and aA³ + bA + cA².
Let A and B be two matrices. If the matrix addition A + B is defined, then prove that (A+B)^t = A^t+B^t. Also, if the matrix product AB is defined then prove that (AB)^t = B^tA^t.
Let A = [a₁,a₂,…,a_n] and B^t = [b₁,b₂,…,b_n]. Then check that order of AB is 1 × 1, whereas BA has order n × n. Determine the matrix products AB and BA.
Let A and B be two matrices such that the matrix product AB is defined.
1. If the first row of A consists entirely of zeros, prove that the first row of AB also consists entirely of zeros.
2. If the first column of B consists entirely of zeros, prove that the first column of AB also consists entirely of zeros.
3. If A has two identical rows then the corresponding rows of AB are also identical.
4. If B has two identical columns then the corresponding columns of AB are also identical.
Let A = and B = . Use the row/column method of matrix multiplication to compute the
1. first row of the matrix AB.
2. third row of the matrix AB.
3. first column of the matrix AB.
4. second column of the matrix AB.
5. first column of B^tA^t.
6. third column of B^tA^t.
7. first row of B^tA^t.
8. second row of B^tA^t.
Let A and B be the matrices given in Exercise 1.2.14.8. Compute A - A^t,(3AB)^t - 4B^tA and 3A - 2A^t.
Let n be a positive integer. Compute Aⁿ for the following matrices: $[ ] ⌊1 1 1⌋ ⌊1 1 1⌋ 1 1 , ⌈0 1 1⌉, ⌈1 1 1⌉ . 0 1 0 0 1 1 1 1$ Can you guess a formula for Aⁿ and prove it by induction?
Construct the matrices A and B satisfying the following statements.
1. The matrix product AB is defined but BA is not defined.
2. The matrix products AB and BA are defined but they have different orders.
3. The matrix products AB and BA are defined and they have the same order but AB≠BA.
Let A be a 3 × 3 matrix satisfying A = . Determine the matrix A.
Let A be a 2 × 2 matrix satisfying A = . Can you construct the matrix A satisfying the above? Why!

1.2.2 Inverse of a Matrix

Definition 1.2.15 (Inverse of a Matrix) Let A be a square matrix of order n.

A square matrix B is said to be a left inverse of A if BA = I_n.
A square matrix C is called a right inverse of A, if AC = I_n.
A matrix A is said to be invertible (or is said to have an inverse) if there exists a matrix B such that AB = BA = I_n.

Lemma 1.2.16 Let A be an n×n matrix. Suppose that there exist n×n matrices B and C such that AB = I_n and CA = I_n, then B = C.

Proof. Note that

C = CIn = C (AB ) = (CA )B = InB = B.

□

Remark 1.2.17

From the above lemma, we observe that if a matrix A is invertible, then the inverse is unique.
As the inverse of a matrix A is unique, we denote it by A^-1. That is, AA^-1 = A^-1A = I.

Example 1.2.18

Let A = .
1. If ad - bc≠0. Then verify that A^-1 = .
2. If ad - bc = 0 then prove that either [ab] = α[cd] for some α ∈ ℝ or [ac] = β[bd] for some β ∈ ℝ. Hence, prove that A is not invertible.
3. In particular, the inverse of equals . Also, the matrices , and do not have inverses.
Let A = . Then A^-1 = .

Theorem 1.2.19 Let A and B be two matrices with inverses A^-1 and B^-1, respectively. Then

(A^-1)^-1 = A.
(AB)^-1 = B^-1A^-1.
(A^t)^-1 = (A^-1)^t.

Proof. Proof of Part 1.
By definition AA^-1 = A^-1A = I. Hence, if we denote A^-1 by B, then we get AB = BA = I. Thus, the definition, implies B^-1 = A, or equivalently (A^-1)^-1 = A.

Proof of Part 2.
Verify that (AB)(B^-1A^-1) = I = (B^-1A^-1)(AB).

Proof of Part 3.
We know AA^-1 = A^-1A = I. Taking transpose, we get

(AA- 1)t = (A -1A)t = It ⇐ ⇒ (A- 1)tAt = At(A -1)t = I.

Hence, by definition (A^t)^-1 = (A^-1)^t. □

We will again come back to the study of invertible matrices in Sections 2.2 and 2.5.

Exercise 1.2.20

Let A be an invertible matrix and let r be a positive integer. Prove that (A^-1)^r = A^-r.
Find the inverse of and .
Let A₁,A₂,…,A_r be invertible matrices. Prove that the product A₁A₂A_r is also an invertible matrix.
Let x^t = [1,2,3] and y^t = [2,-1,4]. Prove that xy^t is not invertible even though x^ty is invertible.
Let A be an n × n invertible matrix. Then prove that
1. A cannot have a row or column consisting entirely of zeros.
2. any two rows of A cannot be equal.
3. any two columns of A cannot be equal.
4. the third row of A cannot be equal to the sum of the first two rows, whenever n ≥ 3.
5. the third column of A cannot be equal to the first column minus the second column, whenever n ≥ 3.
Suppose A is a 2 × 2 matrix satisfying (I + 3A)^-1 = . Determine the matrix A.
Let A be a 3 × 3 matrix such that (I -A)^-1 = . Determine the matrix A [Hint: See Example 1.2.18.2 and Theorem 1.2.19.1].
Let A be a square matrix satisfying A³ + A - 2I = 0. Prove that A^-1 = .
Let A = [a_ij] be an invertible matrix and let p be a nonzero real number. Then determine the inverse of the matrix B = [p^i-ja_ij].

1.3 Some More Special Matrices

Definition 1.3.1

A matrix A over ℝ is called symmetric if A^t = A and skew-symmetric if A^t = -A.
A matrix A is said to be orthogonal if AA^t = A^tA = I.

Example 1.3.2

Let A = and B = . Then A is a symmetric matrix and B is a skew-symmetric matrix.
Let A = . Then A is an orthogonal matrix.
Let A = [a_ij] be an n × n matrix with a_ij equal to 1 if i - j = 1 and 0, otherwise. Then Aⁿ = 0 and A^ℓ≠0 for 1 ≤ ℓ ≤ n-1. The matrices A for which a positive integer k exists such that A^k = 0 are called nilpotent matrices. The least positive integer k for which A^k = 0 is called the order of nilpotency.
Let A = . Then A² = A. The matrices that satisfy the condition that A² = A are called idempotent matrices.

Exercise 1.3.3

Let A be a real square matrix. Then S = (A + A^t) is symmetric, T = (A - A^t) is skew-symmetric, and A = S + T.
Show that the product of two lower triangular matrices is a lower triangular matrix. A similar statement holds for upper triangular matrices.
Let A and B be symmetric matrices. Show that AB is symmetric if and only if AB = BA.
Show that the diagonal entries of a skew-symmetric matrix are zero.
Let A,B be skew-symmetric matrices with AB = BA. Is the matrix AB symmetric or skew-symmetric?
Let A be a symmetric matrix of order n with A² = 0. Is it necessarily true that A = 0?
Let A be a nilpotent matrix. Prove that there exists a matrix B such that B(I + A) = I = (I + A)B [ Hint: If A^k = 0 then look at I - A + A² - + (-1)^k-1A^k-1].

1.3.1 Submatrix of a Matrix

Definition 1.3.4 A matrix obtained by deleting some of the rows and/or columns of a matrix is said to be a submatrix of the given matrix.

For example, if A = [1 4 5]
0 1 2 , a few submatrices of A are

[ ] [ ] [1],[2], 1 ,[15], 1 5 ,A. 0 0 2

But the matrices [ ]
1 4
1 0 and [ ]
1 4
0 2 are not submatrices of A. (The reader is advised to give reasons.)

Let A be an n × m matrix and B be an m × p matrix. Suppose r < m. Then, we can decompose the matrices A and B as A = [PQ] and B = [ ]
H
K ; where P has order n×r and H has order r ×p. That is, the matrices P and Q are submatrices of A and P consists of the first r columns of A and Q consists of the last m - r columns of A. Similarly, H and K are submatrices of B and H consists of the first r rows of B and K consists of the last m - r rows of B. We now prove the following important theorem.

Theorem 1.3.5 Let A = [a_ij] = [PQ] and B = [b_ij] = [ ]
H
K be defined as above. Then

AB = PH + QK.

Proof. First note that the matrices PH and QK are each of order n × p. The matrix products PH and QK are valid as the order of the matrices P,H,Q and K are respectively, n × r,r × p,n × (m - r) and (m - r) × p. Let P = [P_ij],Q = [Q_ij],H = [H_ij], and K = [k_ij]. Then, for 1 ≤ i ≤ n and 1 ≤ j ≤ p, we have

m∑ ∑r m∑ (AB )ij = aikbkj = aikbkj + aikbkj k=r1 k=1m k=r+1 = ∑ P H + ∑ Q K k=1 ik kj k=r+1 ik kj = (P H )ij + (QK )ij = (P H + QK )ij.

□

Remark 1.3.6 Theorem 1.3.5 is very useful due to the following reasons:

The order of the matrices P,Q,H and K are smaller than that of A or B.
It may be possible to block the matrix in such a way that a few blocks are either identity matrices or zero matrices. In this case, it may be easy to handle the matrix product using the block form.
Or when we want to prove results using induction, then we may assume the result for r × r submatrices and then look for (r + 1) × (r + 1) submatrices, etc.

For example, if A = [ ]
1 2 0
2 5 0 and B = ⌊a b⌋
⌈ c d⌉
e f , Then

[ ][ ] [ ] [ ] AB = 1 2 a b + 0 [ef] = a+ 2c b+ 2d . 2 5 c d 0 2a+ 5c 2b + 5d

If A = ⌊0 - 1 2 ⌋
⌈3 1 4 ⌉
-2 5 - 3 , then A can be decomposed as follows:

: A = , or A = , or
: A = and so on.

Suppose A =

m₁m₂

n₁

n₂

and B =

s₁s₂

r₁

r₂

. Then the matrices P,Q,R,S and E,F,G,H, are called the blocks of the matrices A and B, respectively.

Even if A + B is defined, the orders of P and E may not be same and hence, we may not be able to add A and B in the block form. But, if A + B and P + E is defined then A + B = [ ]
P + E Q + F
R+ G S + H .

Similarly, if the product AB is defined, the product PE need not be defined. Therefore, we can talk of matrix product AB as block product of matrices, if both the products AB and PE are defined. And in this case, we have AB = [ ]
P E + QG PF + QH
RE + SG RF + SH .

That is, once a partition of A is fixed, the partition of B has to be properly chosen for purposes of block addition or multiplication.

Exercise 1.3.7

Complete the proofs of Theorems 1.2.5 and 1.2.13.
Let A = ,B = and C = . Compute
1. the first row of AC,
2. the first row of B(AC),
3. the second row of B(AC), and
4. the third row of B(AC).
5. Let x^t = [1,1,1,-1]. Compute the matrix product Cx.
Let x = and y = . Determine the 2 × 2 matrix
1. A such that the y = Ax gives rise to counter-clockwise rotation through an angle α.
2. B such that y = Bx gives rise to the reflection along the line y = (tanγ)x.
  Now, let C and D be two 2×2 matrices such that y = Cx gives rise to counter-clockwise rotation through an angle β and y = Dx gives rise to the reflection along the line y = (tanδ)x, respectively. Then prove that
3. y = (AC)x or y = (CA)x give rise to counter-clockwise rotation through an angle α+β.
4. y = (BD)x or y = (DB)x give rise to rotations. Which angles do they represent?
5. What can you say about y = (AB)x or y = (BA)x ?
Let A = ,B = and C = . If x = and y = then geometrically interpret the following:
1. y = Ax,y = Bx and y = Cx.
2. y = (BC)x,y = (CB)x,y = (BA)x and y = (AB)x.
Consider the two coordinate transformations
x₁
= a₁₁y₁ + a₁₂y₂

x₂
= a₂₁y₁ + a₂₂y₂

and
y₁
= b₁₁z₁ + b₁₂z₂

y₂
= b₂₁z₁ + b₂₂z₂

.
1. Compose the two transformations to express x₁,x₂ in terms of z₁,z₂.
2. If x^t = [x₁,x₂],y^t = [y₁,y₂] and z^t = [z₁,z₂] then find matrices A,B and C such that x = Ay,y = Bz and x = Cz.
3. Is C = AB?
Let A be an n × n matrix. Then trace of A, denoted tr(A), is defined as $tr(A ) = a + a + ⋅⋅⋅a . 11 22 nn$
1. Let A = and B = . Compute tr(A) and tr(B).
2. Then for two square matrices, A and B of the same order, prove that
  1. tr (A + B) = tr (A) + tr (B).
  2. tr (AB) = tr (BA).
3. Prove that there do not exist matrices A and B such that AB - BA = cI_n for any c≠0.
Let A and B be two m × n matrices with real entries. Then prove that
1. Ax = 0 for all n × 1 vector x with real entries implies A = 0, the zero matrix.
2. Ax = Bx for all n × 1 vector x with real entries implies A = B.
Let A be an n×n matrix such that AB = BA for all n×n matrices B. Show that A = αI for some α ∈ ℝ.
Let A = .
1. Find a matrix B such that AB = I₂.
2. What can you say about the number of such matrices? Give reasons for your answer.
3. Does there exist a matrix C such that CA = I₃? Give reasons for your answer.
Let A = and B = . Compute the matrix product AB using the block matrix multiplication.
Let A = . If P,Q,R and S are symmetric, is the matrix A symmetric? If A is symmetric, is it necessary that the matrices P,Q,R and S are symmetric?
Let A be a 3 × 3 matrix and let A = , where A₁₁ is a 2 × 2 invertible matrix and c is a real number.
1. If p = c - A₂₁A₁₁^-1A₁₂ is non-zero, prove that B = is the inverse of A, where B₁₁ = A₁₁^-1 + A₁₁^-1A₁₂p^-1A₂₁A₁₁^-1, B₁₂ = -A₁₁^-1A₁₂p^-1 and B₂₁ = -p^-1A₂₁A₁₁^-1.
2. Find the inverse of the matrices and .
Let x be an n × 1 matrix satisfying x^tx = 1.
1. Define A = I_n - 2xx^t. Prove that A is symmetric and A² = I. The matrix A is commonly known as the Householder matrix.
2. Let α≠1 be a real number and define A = I_n - αxx^t. Prove that A is symmetric and invertible [Hint: the inverse is also of the form I_n + βxx^t for some value of β].
Let A be an n × n invertible matrix and let x and y be two n × 1 matrices. Also, let β be a real number such that α = 1 + βy^tA^-1x≠0. Then prove the famous Shermon-Morrison formula $(A + βxyt)-1 = A -1 - β-A- 1xytA -1. α$ This formula gives the information about the inverse when an invertible matrix is modified by a rank one matrix.
Let J be an n × n matrix having each entry 1.
1. Prove that J² = nJ.
2. Let α₁,α₂,β₁,β₂ ∈ ℝ. Prove that there exist α₃,β₃ ∈ ℝ such that $(α1In + β1J)⋅(α2In + β2J) = α3In + β3J.$
3. Let α,β ∈ with α≠0 and α+nβ≠0 and define A = αI_n+βJ. Prove that A is invertible.
Let A be an upper triangular matrix. If A^*A = AA^* then prove that A is a diagonal matrix. The same holds for lower triangular matrix.

1.4 Summary

In this chapter, we started with the definition of a matrix and came across lots of examples. In particular, the following examples were important:

The zero matrix of size m × n, denoted 0_m×n or 0.
The identity matrix of size n × n, denoted I_n or I.
Triangular matrices
Hermitian/Symmetric matrices
Skew-Hermitian/skew-symmetric matrices
Unitary/Orthogonal matrices

We also learnt product of two matrices. Even though it seemed complicated, it basically tells the following:

Multiplying by a matrix on the left to a matrix A is same as row operations.
Multiplying by a matrix on the right to a matrix A is same as column operations.

Chapter 2
System of Linear Equations

2.1 Introduction

Let us look at some examples of linear systems.

Suppose a,b ∈ ℝ. Consider the system ax = b.
1. If a≠0 then the system has a unique solution x = .
2. If a = 0 and
  1. b≠0 then the system has no solution.
  2. b = 0 then the system has infinite number of solutions, namely all x ∈ ℝ.
Consider a system with 2 equations in 2 unknowns. The equation ax + by = c represents a line in ℝ² if either a≠0 or b≠0. Thus the solution set of the system $a1x+ b1y = c1,a2x+ b2y = c2$ is given by the points of intersection of the two lines. The different cases are illustrated by examples (see Figure 1).
1. Unique Solution
  x + 2y = 1 and x + 3y = 1. The unique solution is (x,y)^t = (1,0)^t.
  Observe that in this case, a₁b₂ - a₂b₁≠0.
2. Infinite Number of Solutions
  x + 2y = 1 and 2x + 4y = 2. The solution set is (x,y)^t = (1 - 2y,y)^t = (1,0)^t + y(-2,1)^t with y arbitrary as both the equations represent the same line. Observe the following:
  1. Here, a₁b₂ - a₂b₁ = 0,a₁c₂ - a₂c₁ = 0 and b₁c₂ - b₂c₁ = 0.
  2. The vector (1,0)^t corresponds to the solution x = 1,y = 0 of the given system whereas the vector (-2,1)^t corresponds to the solution x = -2,y = 1 of the system x + 2y = 0,2x + 4y = 0.
3. No Solution
  x + 2y = 1 and 2x + 4y = 3. The equations represent a pair of parallel lines and hence there is no point of intersection. Observe that in this case, a₁b₂ - a₂b₁ = 0 but a₁c₂ - a₂c₁≠0.
As a last example, consider 3 equations in 3 unknowns.
A linear equation ax + by + cz = d represent a plane in ℝ³ provided (a,b,c)≠(0,0,0). Here, we have to look at the points of intersection of the three given planes.
1. Unique Solution
  Consider the system x + y + z = 3,x + 4y + 2z = 7 and 4x + 10y - z = 13. The unique solution to this system is (x,y,z)^t = (1,1,1)^t; i.e. the three planes intersect at a point.
2. Infinite Number of Solutions
  Consider the system x + y + z = 3,x + 2y + 2z = 5 and 3x + 4y + 4z = 11. The solution set is (x,y,z)^t = (1,2 - z,z)^t = (1,2,0)^t + z(0,-1,1)^t, with z arbitrary. Observe the following:
  1. Here, the three planes intersect in a line.
  2. The vector (1,2,0)^t corresponds to the solution x = 1,y = 2 and z = 0 of the linear system x + y + z = 3,x + 2y + 2z = 5 and 3x + 4y + 4z = 11. Also, the vector (0,-1,1)^t corresponds to the solution x = 0,y = -1 and z = 1 of the linear system x + y + z = 0,x + 2y + 2z = 0 and 3x + 4y + 4z = 0.
3. No Solution
  The system x + y + z = 3,x + 2y + 2z = 5 and 3x + 4y + 4z = 13 has no solution. In this case, we get three parallel lines as intersections of the above planes, namely
  1. a line passing through (1,2,0) with direction ratios (0,-1,1),
  2. a line passing through (3,1,0) with direction ratios (0,-1,1), and
  3. a line passing through (-1,4,0) with direction ratios (0,-1,1).
  The readers are advised to supply the proof.

Definition 2.1.1 (Linear System) A system of m linear equations in n unknowns x₁,x₂,…,x_n is a set of equations of the form

a11x1 + a12x2 + ⋅⋅⋅+a1nxn = b1 a x + a x + ⋅⋅⋅+a x = b 21. 1 22 2 2n n .2 .. .. (2.1.1) am1x1 + am2x2 + ⋅⋅⋅+ amnxn = bm

where for 1 ≤ i ≤ n, and 1 ≤ j ≤ m;a_ij,b_i ∈ ℝ. Linear System (2.1.1) is called homogeneous if b₁ = 0 = b₂ =

= b_m and non-homogeneous otherwise.

We rewrite the above equations in the form Ax = b, where
A = ⌊ ⌋
|a11 a12 ⋅⋅⋅ a1n |
||a21 a22 ⋅⋅⋅ a2n ||
⌈... ... ... ... ⌉
am1 am2 ⋅⋅⋅ amn ,x = ⌊ ⌋
| x1|
|| x2||
⌈ ... ⌉
xn , and b = ⌊ ⌋
| b1|
|| b2||
⌈ ... ⌉
bm

The matrix A is called the coefficient matrix and the block matrix [Ab ] , is called the augmented matrix of the linear system (2.1.1).

Remark 2.1.2

The first column of the augmented matrix corresponds to the coefficients of the variable x₁.
In general, the j^th column of the augmented matrix corresponds to the coefficients of the variable x_j, for j = 1,2,…,n.
The (n + 1)^th column of the augmented matrix consists of the vector b.
The i^th row of the augmented matrix represents the i^th equation for i = 1,2,…,m.
That is, for i = 1,2,…,m and j = 1,2,…,n, the entry a_ij of the coefficient matrix A corresponds to the i^th linear equation and the j^th variable x_j.

Definition 2.1.3 For a system of linear equations Ax = b, the system Ax = 0 is called the associated homogeneous system.

Definition 2.1.4 (Solution of a Linear System) A solution of Ax = b is a column vector y with entries y₁,y₂,…,y_n such that the linear system (2.1.1) is satisfied by substituting y_i in place of x_i . The collection of all solutions is called the solution set of the system.

That is, if y^t = [y₁,y₂,…,y_n] is a solution of the linear system Ax = b then Ay = b holds. For example, from Example 3.3a, we see that the vector y^t = [1,1,1] is a solution of the system Ax = b, where A = ⌊1 1 1⌋
⌈1 4 2⌉

4 10 - 1 ,x^t = [x,y,z] and b^t = [3,7,13].

We now state a theorem about the solution set of a homogeneous system. The readers are advised to supply the proof.

Theorem 2.1.5 Consider the homogeneous linear system Ax = 0. Then

The zero vector, 0 = (0,…,0)^t, is always a solution, called the trivial solution.
Suppose x₁,x₂ are two solutions of Ax = 0. Then k₁x₁ + k₂x₂ is also a solution of Ax = 0 for any k₁,k₂ ∈ ℝ.

Remark 2.1.6

A non-zero solution of Ax = 0 is called a non-trivial solution.
If Ax = 0 has a non-trivial solution, say y≠0 then z = cy for every c ∈ ℝ is also a solution. Thus, the existence of a non-trivial solution of Ax = 0 is equivalent to having an infinite number of solutions for the system Ax = 0.
If u,v are two distinct solutions of Ax = b then one has the following:
1. u - v is a solution of the system Ax = 0.
2. Define x_h = u - v. Then x_h is a solution of the homogeneous system Ax = 0.
3. That is, any two solutions of Ax = b differ by a solution of the associated homogeneous system Ax = 0.
4. Or equivalently, the set of solutions of the system Ax = b is of the form, {x₀+x_h}; where x₀ is a particular solution of Ax = b and x_h is a solution of the associated homogeneous system Ax = 0.

2.1.1 A Solution Method

Example 2.1.7 Solve the linear system y + z = 2,2x + 3z = 5,x + y + z = 3.

Solution: In this case, the augmented matrix is ⌊ ⌋
0 1 1 2
⌈ 2 0 3 5⌉
1 1 1 3 and the solution method proceeds along the following steps.

Interchange 1^st and 2^nd equation. $2x + 3z = 5 ⌊2 0 3 5⌋ ⌈ ⌉ y + z = 2 0 1 1 2 . x+ y+ z = 3 1 1 1 3$
Replace 1^st equation by 1^st equation times . $x + 3z = 5 ⌊1 0 3 5⌋ y+ 2z = 22 ⌈0 1 21 22⌉ . x + y+ z = 3 1 1 1 3$
Replace 3^rd equation by 3^rd equation minus the 1^st equation. $x + 3z = 5 ⌊ 1 0 3 5⌋ y +2z = 22 ⌈ 0 1 21 22⌉ . 1 1 1 1 y- 2z = 2 0 1 - 2 2$
Replace 3^rd equation by 3^rd equation minus the 2^nd equation. $x + 3z = 5 ⌊ 1 0 3 5 ⌋ y+ 2z = 22 ⌈ 0 1 21 22 ⌉. 3 3 3 3 - 2z = -2 0 0 - 2 - 2$
Replace 3^rd equation by 3^rd equation times . $x + 32z = 52 ⌊1 0 32 52⌋ y+ z = 2 ⌈0 1 1 2⌉ . z = 1 0 0 1 1$

The last equation gives z = 1. Using this, the second equation gives y = 1. Finally, the first equation gives x = 1. Hence the solution set is {(x,y,z)^t : (x,y,z) = (1,1,1)}, a unique solution.

In Example 2.1.7, observe that certain operations on equations (rows of the augmented matrix) helped us in getting a system in Item 5, which was easily solvable. We use this idea to define elementary row operations and equivalence of two linear systems.

Definition 2.1.8 (Elementary Row Operations) Let A be an m×n matrix. Then the elementary row operations are defined as follows:

R_ij : Interchange of the i^th and the j^th row of A.
For c≠0, R_k(c): Multiply the k^th row of A by c.
For c≠0, R_ij(c): Replace the j^th row of A by the j^th row of A plus c times the i^th row of A.

Definition 2.1.9 (Equivalent Linear Systems) Let [Ab] and [Cd] be augmented matrices of two linear systems. Then the two linear systems are said to be equivalent if [Cd] can be obtained from [Ab] by application of a finite number of elementary row operations.

Definition 2.1.10 (Row Equivalent Matrices) Two matrices are said to be row-equivalent if one can be obtained from the other by a finite number of elementary row operations.

Thus, note that linear systems at each step in Example 2.1.7 are equivalent to each other. We also prove the following result that relates elementary row operations with the solution set of a linear system.

Lemma 2.1.11 Let Cx = d be the linear system obtained from Ax = b by application of a single elementary row operation. Then Ax = b and Cx = d have the same solution set.

Proof. We prove the result for the elementary row operation R_jk(c) with c≠0. The reader is advised to prove the result for other elementary operations.

In this case, the systems Ax = b and Cx = d vary only in the k^th equation. Let (α₁,α₂,…,α_n) be a solution of the linear system Ax = b. Then substituting for α_i’s in place of x_i’s in the k^th and j^th equations, we get

a α + a α + ⋅⋅⋅a α = b,and a α + a α + ⋅⋅⋅a α = b . k1 1 k2 2 kn n k j1 1 j2 2 jn n j

Therefore,

(ak1 + caj1)α1 + (ak2 + caj2)α2 + ⋅⋅⋅+ (akn + cajn)αn = bk + cbj.

(2.1.2)

But then the k^th equation of the linear system Cx = d is

(ak1 + caj1)x1 + (ak2 + caj2)x2 + ⋅⋅⋅+ (akn + cajn)xn = bk + cbj.

(2.1.3)

Therefore, using Equation (2.1.2), (α₁,α₂,…,α_n) is also a solution for k^th Equation (2.1.3).

Use a similar argument to show that if (β₁,β₂,…,β_n) is a solution of the linear system Cx = d then it is also a solution of the linear system Ax = b. Hence, the required result follows. □

The readers are advised to use Lemma 2.1.11 as an induction step to prove the main result of this subsection which is stated next.

Theorem 2.1.12 Two equivalent linear systems have the same solution set.

2.1.2 Gauss Elimination Method

We first define the Gauss elimination method and give a few examples to understand the method.

Definition 2.1.13 (Forward/Gauss Elimination Method) The Gaussian elimination method is a procedure for solving a linear system Ax = b (consisting of m equations in n unknowns) by bringing the augmented matrix

| ⌊ a11 a12 ⋅⋅⋅ a1m ⋅⋅⋅ a1n |b1 ⌋ | a21 a22 ⋅⋅⋅ a2m ⋅⋅⋅ a2n |b2 | [Ab] = || .. .. .. .. .. | .. || ⌈ . . . . . | . ⌉ am1 am2 ⋅⋅⋅ amm ⋅⋅⋅ amn |bm

to an upper triangular form

⌊ | ⌋ c11 c12 ⋅⋅⋅ c1m ⋅⋅⋅ c1n |d1 || 0 c22 ⋅⋅⋅ c2m ⋅⋅⋅ c2n |d2 || |⌈ .. .. .. .. .. |.. |⌉ . . . . . |. 0 0 ⋅⋅⋅ cmm ⋅⋅⋅ cmn |dm

by application of elementary row operations. This elimination process is also called the forward elimination method.

We have already seen an example before defining the notion of row equivalence. We give two more examples to illustrate the Gauss elimination method.

Example 2.1.14 Solve the following linear system by Gauss elimination method.

x + y+ z = 3,x + 2y+ 2z = 5,3x + 4y+ 4z = 11

Solution: Let A = ⌊ ⌋
1 1 1
⌈1 2 2⌉
3 4 4 and b = ⌊ ⌋
3
⌈ 5⌉
11 . The Gauss Elimination method starts with the augmented matrix [Ab] and proceeds as follows:

Replace 2^nd equation by 2^nd equation minus the 1^st equation. $⌊ ⌋ x+ y+ z = 3 ⌈1 1 1 3⌉ y + z = 2 0 1 1 2 . 3x + 4y+ 4z = 11 3 4 4 11$
Replace 3^rd equation by 3^rd equation minus 3 times 1^st equation. $⌊ ⌋ x+ y+ z = 3 ⌈1 1 1 3⌉ y + z = 2 0 1 1 2 . y + z = 2 0 1 1 2$
Replace 3^rd equation by 3^rd equation minus the 2^nd equation. $⌊ ⌋ x+ y+ z = 3 1 1 1 3 y + z = 2 ⌈0 1 1 2⌉ . 0 0 0 0$

Thus, the solution set is {(x,y,z)^t : (x,y,z) = (1,2-z,z)} or equivalently {(x,y,z)^t : (x,y,z) = (1,2,0)+z(0,-1,1)}, with z arbitrary. In other words, the system has infinite number of solutions. Observe that the vector y^t = (1,2,0) satisfies Ay = b and the vector z^t = (0,-1,1) is a solution of the homogeneous system Ax = 0.

Example 2.1.15 Solve the following linear system by Gauss elimination method.

x + y+ z = 3,x + 2y+ 2z = 5,3x + 4y+ 4z = 12

Solution: Let A = ⌊ ⌋
1 1 1
⌈1 2 2⌉
3 4 4 and b = ⌊ ⌋
3
⌈ 5⌉
12 . The Gauss Elimination method starts with the augmented matrix [Ab] and proceeds as follows:

Replace 2^nd equation by 2^nd equation minus the 1^st equation. $⌊ ⌋ x+ y+ z = 3 ⌈1 1 1 3⌉ y + z = 2 0 1 1 2 . 3x + 4y+ 4z = 12 3 4 4 12$
Replace 3^rd equation by 3^rd equation minus 3 times 1^st equation. $x+ y+ z = 3 ⌊1 1 1 3⌋ y + z = 2 ⌈0 1 1 2⌉ . y + z = 3 0 1 1 3$
Replace 3^rd equation by 3^rd equation minus the 2^nd equation. $x+ y+ z = 3 ⌊1 1 1 3⌋ y + z = 2 ⌈0 1 1 2⌉ . 0 = 1 0 0 0 1$

The third equation in the last step is

0x + 0y+ 0z = 1.

This can never hold for any value of x,y,z. Hence, the system has no solution.

Remark 2.1.16 Note that to solve a linear system Ax = b, one needs to apply only the row operations to the augmented matrix [Ab].

Definition 2.1.17 (Row Echelon Form of a Matrix) A matrix C is said to be in the row echelon form if

the rows consisting entirely of zeros appears after the non-zero rows,
the first non-zero entry in a non-zero row is 1. This term is called the leading term or a leading 1. The column containing this term is called the leading column.
In any two successive non-rows, the leading 1 in the lower row occurs farther to the right than the leading 1 in the higher row.

Example 2.1.18 The matrices ⌊ ⌋
0 1 4 2
|⌈0 0 1 1|⌉

0 0 0 0 and ⌊ ⌋
1 1 0 2 3
|| 0 0 0 1 4 ||
⌈ ⌉
0 0 0 0 1 are in row-echelon form. Whereas, the matrices

⌊ ⌋ ⌊ ⌋ ⌊ 0 1 4 2⌋ 1 1 0 2 3 1 1 0 2 3 | | || || || || ⌈ 0 0 0 0⌉ ,⌈ 0 0 0 1 4 ⌉ and ⌈ 0 0 0 0 1 ⌉ 0 0 1 1 0 0 0 0 2 0 0 0 1 4

are not in row-echelon form.

Definition 2.1.19 (Basic, Free Variables) Let Ax = b be a linear system consisting of m equations in n unknowns. Suppose the application of Gauss elimination method to the augmented matrix [Ab] yields the matrix [Cd].

Then the variables corresponding to the leading columns (in the first n columns of [Cd]) are called the basic variables.
The variables which are not basic are called free variables.

The free variables are called so as they can be assigned arbitrary values. Also, the basic variables can be written in terms of the free variables and hence the value of basic variables in the solution set depend on the values of the free variables.

Remark 2.1.20 Observe the following:

In Example 2.1.14, the solution set was given by $(x,y,z) = (1,2 - z,z) = (1,2,0)+ z(0,- 1,1), with z arbitrary.$ That is, we had x,y as two basic variables and z as a free variable.
Example 2.1.15 didn’t have any solution because the row-echelon form of the augmented matrix had a row of the form [0,0,0,1].
Suppose the application of row operations to [Ab] yields the matrix [Cd] which is in row echelon form. If [Cd] has r non-zero rows then [Cd] will consist of r leading terms or r leading columns. Therefore, the linear system Ax = b will have r basic variables and n-r free variables.

Before proceeding further, we have the following definition.

Definition 2.1.21 (Consistent, Inconsistent) A linear system is called consistent if it admits a solution and is called inconsistent if it admits no solution.

We are now ready to prove conditions under which the linear system Ax = b is consistent or inconsistent.

Theorem 2.1.22 Consider the linear system Ax = b, where A is an m × n matrix and x^t = (x₁ , x₂,…,x_n). If one obtains [Cd] as the row-echelon form of [Ab] with d^t = (d₁,d₂,…,d_m) then

Ax = b is inconsistent (has no solution) if [Cd] has a row of the form [0^t1], where 0^t = (0,…,0).
Ax = b is consistent (has a solution) if [Cd] has no row of the form [0^t1]. Furthermore,
1. if the number of variables equals the number of leading terms then Ax = b has a unique solution.
2. if the number of variables is strictly greater than the number of leading terms then Ax = b has infinite number of solutions.

Proof. Part 1: The linear equation corresponding to the row [0^t1] equals

0x1 + 0x2 + ⋅⋅⋅+ 0xn = 1.

Obviously, this equation has no solution and hence the system Cx = d has no solution. Thus, by Theorem 2.1.12, Ax = b has no solution. That is, Ax = b is inconsistent.

Part 2: Suppose [Cd] has r non-zero rows. As [Cd] is in row echelon form there exist positive integers 1 ≤ i₁ < i₂ < … < i_r ≤ n such that entries c_{ℓi_ℓ} for 1 ≤ ℓ ≤ r are leading terms. This in turn implies that the variables x_{i_j}, for 1 ≤ j ≤ r are the basic variables and the remaining n - r variables, say x_t₁,x_t₂,…,x_{t_n-r}, are free variables. So for each ℓ,1 ≤ ℓ ≤ r, one obtains x_{i_ℓ} + ∑ _{k>i_ℓ}c_ℓkx_k = d_ℓ (k > i_ℓ in the summation as [Cd] is an upper triangular matrix). Or equivalently,

r n-r x = d - ∑ c x - ∑ c x for 1 ≤ l ≤ r. iℓ ℓ j=ℓ+1 ℓij ij s=1 ℓts ts

Hence, a solution of the system Cx = d is given by

∑r xts= 0 for s = 1,...,n - r and xir = dr,xir-1 = dr-1 - dr,...,xi1 = d1 - cℓijdj. j=2

Thus, by Theorem 2.1.12 the system Ax = b is consistent. In case of Part 2a, there are no free variables and hence the unique solution is given by

n x = d ,x = d - d ,...,x = d - ∑ c d . n n n- 1 n-1 n 1 1 j=2 ℓij j

In case of Part 2b, there is at least one free variable and hence Ax = b has infinite number of solutions. Thus, the proof of the theorem is complete. □

We omit the proof of the next result as it directly follows from Theorem 2.1.22.

Corollary 2.1.23 Consider the homogeneous system Ax = 0. Then

Ax = 0 is always consistent as 0 is a solution.
If m < n then n - m > 0 and there will be at least n - m free variables. Thus Ax = 0 has infinite number of solutions. Or equivalently, Ax = 0 has a non-trivial solution.

We end this subsection with some applications related to geometry.

Example 2.1.24

Determine the equation of the line/circle that passes through the points (-1,4),(0,1) and (1,4).
Solution: The general equation of a line/circle in 2-dimensional plane is given by a(x² + y²) + bx + cy + d = 0, where a,b,c and d are the unknowns. Since this curve passes through the given points, we have
$2 2 a((- 1) + 4 )+ (- 1)b+ 4c+ d = = 0 a((0)2 +12)+ (0)b+ 1c+ d = = 0 a((1)2 +42)+ (1)b+ 4c+ d = = 0.$
Solving this system, we get (a,b,c,d) = (d,0,-d,d). Hence, taking d = 13, the equation of the required circle is $3(x2 + y2)- 16y + 13 = 0.$
Determine the equation of the plane that contains the points (1,1,1),(1,3,2) and (2,-1,2).
Solution: The general equation of a plane in 3-dimensional space is given by ax + by + cz + d = 0, where a,b,c and d are the unknowns. Since this plane passes through the given points, we have
$a+ b+ c+ d = = 0 a+ 3b+ 2c+ d = = 0 2a- b+ 2c+ d = = 0.$
Solving this system, we get (a,b,c,d) = (-d,-,-d,d). Hence, taking d = 3, the equation of the required plane is -4x - y + 2z + 3 = 0.
Let A = .
1. Find a non-zero x^t ∈ ℝ³ such that Ax = 2x.
2. Does there exist a non-zero vector y^t ∈ ℝ³ such that Ay = 4y?
Solution of Part 3a: Solving for Ax = 2x is same as solving for (A - 2I)x = 0. This leads to the augmented matrix . Check that a non-zero solution is given by x^t = (1,0,0).
Solution of Part 3b: Solving for Ay = 4y is same as solving for (A - 4I)y = 0. This leads to the augmented matrix . Check that a non-zero solution is given by y^t = (2,0,1).

Exercise 2.1.25

Determine the equation of the curve y = ax² + bx + c that passes through the points (-1,4),(0,1) and (1,4).
Solve the following linear system.
1. x + y + z + w = 0,x - y + z + w = 0 and -x + y + 3z + 3w = 0.
2. x + 2y = 1,x + y + z = 4 and 3y + 2z = 1.
3. x + y + z = 3,x + y - z = 1 and x + y + 7z = 6.
4. x + y + z = 3,x + y - z = 1 and x + y + 4z = 6.
5. x + y + z = 3,x + y - z = 1,x + y + 4z = 6 and x + y - 4z = -1.
For what values of c and k, the following systems have i) no solution, ii) a unique solution and iii) infinite number of solutions.
1. x + y + z = 3,x + 2y + cz = 4,2x + 3y + 2cz = k.
2. x + y + z = 3,x + y + 2cz = 7,x + 2y + 3cz = k.
3. x + y + 2z = 3,x + 2y + cz = 5,x + 2y + 4z = k.
4. kx + y + z = 1,x + ky + z = 1,x + y + kz = 1.
5. x + 2y - z = 1,2x + 3y + kz = 3,x + ky + 3z = 2.
6. x - 2y = 1,x - y + kz = 1,ky + 4z = 6.
For what values of a, does the following systems have i) no solution, ii) a unique solution and iii) infinite number of solutions.
1. x + 2y + 3z = 4,2x + 5y + 5z = 6,2x + (a² - 6)z = a + 20.
2. x + y + z = 3,2x + 5y + 4z = a,3x + (a² - 8)z = 12.
Find the condition(s) on x,y,z so that the system of linear equations given below (in the unknowns a, b and c) is consistent?
1. a + 2b - 3c = x,2a + 6b - 11c = y,a - 2b + 7c = z
2. a + b + 5c = x,a + 3c = y,2a - b + 4c = z
3. a + 2b + 3c = x,2a + 4b + 6c = y,3a + 6b + 9c = z
Let A be an n×n matrix. If the system A²x = 0 has a non trivial solution then show that Ax = 0 also has a non trivial solution.
Prove that we need to have 5 set of distinct points to specify a general conic in 2-dimensional plane.
Let u^t = (1,1,-2) and v^t = (-1,2,3). Find condition on x,y and z such that the system cu^t + dv^t = (x,y,z) in the unknowns c and d is consistent.

2.1.3 Gauss-Jordan Elimination

The Gauss-Jordan method consists of first applying the Gauss Elimination method to get the row-echelon form of the matrix [Ab] and then further applying the row operations as follows. For example, consider Example 2.1.7. We start with Step 5 and apply row operations once again. But this time, we start with the 3^rd row.

Replace 2^nd equation by 2^nd equation minus the 3^rd equation. $3 5 ⌊ 3 5⌋ x + 2z = 2 ⌈1 0 2 2⌉ y = 2 0 1 0 1 . z = 1 0 0 1 1$
Replace 1^st equation by 1^st equation minus times 3^rd equation. $x = 1 ⌊1 0 0 1⌋ ⌈ ⌉. y = 1 0 1 0 1 z = 1 0 0 1 1$
Thus, the solution set equals {(x,y,z)^t : (x,y,z) = (1,1,1)}.

Definition 2.1.26 (Row-Reduced Echelon Form) A matrix C is said to be in the row-reduced echelon form or reduced row echelon form if

C is already in the row echelon form;
the leading column containing the leading 1 has every other entry zero.

A matrix which is in the row-reduced echelon form is also called a row-reduced echelon matrix.

Example 2.1.27 Let A = ⌊ ⌋
| 0 1 4 2|
⌈ 0 0 1 1⌉
0 0 0 0 and B = ⌊ ⌋
| 1 1 0 2 3 |
|⌈ 0 0 0 1 4 |⌉
0 0 0 0 1 . Then A and B are in row echelon form. If C and D are the row-reduced echelon forms of A and B, respectively then C = ⌊ ⌋
|0 1 0 - 2|
⌈0 0 1 1 ⌉
0 0 0 0 and D = ⌊ 1 1 0 0 0 ⌋
|| ||
⌈ 0 0 0 1 0 ⌉
0 0 0 0 1 .

Definition 2.1.28 (Back Substitution/Gauss-Jordan Method) The procedure to get The row-reduced echelon matrix from the row-echelon matrix is called the back substitution. The elimination process applied to obtain the row-reduced echelon form of the augmented matrix is called the Gauss-Jordan elimination method.

That is, the Gauss-Jordan elimination method consists of both the forward elimination and the backward substitution.

Remark 2.1.29 Note that the row reduction involves only row operations and proceeds from left to right. Hence, if A is a matrix consisting of first s columns of a matrix C, then the row-reduced form of A will consist of the first s columns of the row-reduced form of C.

The proof of the following theorem is beyond the scope of this book and is omitted.

Theorem 2.1.30 The row-reduced echelon form of a matrix is unique.

Remark 2.1.31 Consider the linear system Ax = b. Then Theorem 2.1.30 implies the following:

The application of the Gauss Elimination method to the augmented matrix may yield different matrices even though it leads to the same solution set.
The application of the Gauss-Jordan method to the augmented matrix yields the same matrix and also the same solution set even though we may have used different sequence of row operations.

Example 2.1.32 Consider Ax = b, where A is a 3 × 3 matrix. Let [Cd] be the row-reduced echelon form of [Ab]. Also, assume that the first column of A has a non-zero entry. Then the possible choices for the matrix [Cd] with respective solution sets are given below:

. Ax = b has a unique solution, (x,y,z) = (d₁,d₂,d₃).
, or . Ax = b has no solution for any choice of α,β.
,,. Ax = b has Infinite number of solutions for every choice of α,β.

Exercise 2.1.33

Let Ax = b be a linear system in 2 unknowns. What are the possible choices for the row-reduced echelon form of the augmented matrix [Ab]?
Find the row-reduced echelon form of the following matrices: $⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌊- 1 - 1 - 2 3 ⌋ 0 0 1 0 1 1 3 0 - 1 1 | | ⌈1 0 3⌉ ,⌈0 0 1 3⌉,⌈ - 2 0 3⌉ ,|⌈ 3 3 - 3 - 3|⌉. 3 0 7 1 1 0 0 - 5 1 0 1 1 2 2 - 1 - 1 2 - 2$
Find all the solutions of the following system of equations using Gauss-Jordan method. No other method will be accepted.

x + y – 2 u + v = 2
z + u + 2 v = 3
v + w = 3
v + 2 w = 5

2.2 Elementary Matrices

In the previous section, we solved a system of linear equations with the help of either the Gauss Elimination method or the Gauss-Jordan method. These methods required us to make row operations on the augmented matrix. Also, we know that (see Section 1.2.1 ) the row-operations correspond to multiplying a matrix on the left. So, in this section, we try to understand the matrices which helped us in performing the row-operations and also use this understanding to get some important results in the theory of square matrices.

Definition 2.2.1 A square matrix E of order n is called an elementary matrix if it is obtained by applying exactly one row operation to the identity matrix, I_n.

Remark 2.2.2 Fix a positive integer n. Then the elementary matrices of order n are of three types and are as follows:

E_ij corresponds to the interchange of the i^th and the j^th row of I_n.
For c≠0, E_k(c) is obtained by multiplying the k^th row of I_n by c.
For c≠0, E_ij(c) is obtained by replacing the j^th row of I_n by the j^th row of I_n plus c times the i^th row of I_n.

Example 2.2.3

In particular, for n = 3 and a real number c≠0, one has $⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌈1 0 0⌉ ⌈c 0 0⌉ ⌈1 0 0⌉ E23 = 0 0 1 ,E1 (c) = 0 1 0 , and E32(c) = 0 1 c . 0 1 0 0 0 1 0 0 1$
Let A = and B = . Then B is obtained from A by the interchange of 2^nd and 3^rd row. Verify that $⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌈1 0 0⌉ ⌈1 2 3 0⌉ ⌈1 2 3 0⌉ E23A = 0 0 1 2 0 3 4 = 3 4 5 6 = B. 0 1 0 3 4 5 6 2 0 3 4$
Let A = . Then B = is the row-reduced echelon form of A. The readers are advised to verify that $B = E32(- 1) ⋅E21(- 1)⋅E3(1∕3)⋅E23(2)⋅E23 ⋅E12(- 2)⋅E13 ⋅A.$ Or equivalently, check that
$⌊ ⌋ ⌊ ⌋ 1 1 1 3 1 1 1 3 E13A = A1 = ⌈2 0 3 5⌉,E12(- 2)A1 = A2 = ⌈0 - 2 1 - 1⌉, 0 1 1 2 0 1 1 2 ⌊1 1 1 3 ⌋ ⌊ 1 1 1 3⌋ ⌈ ⌉ ⌈ ⌉ E23A2 = A3 = 0 1 1 2 ,E23(2)A3 = A4 = 0 1 1 2 , 0 - 2 1 - 1 0 0 3 3 ⌊1 1 1 3⌋ ⌊1 0 0 1⌋ E3(1∕3)A4 = A5 = ⌈0 1 1 2⌉,E21(- 1)A5 = A6 = ⌈0 1 1 2⌉, 0 0 1 1 0 0 1 1 ⌊ ⌋ 1 0 0 1 E32(- 1)A6 = B = ⌈ 0 1 0 1⌉ . 0 0 1 1$

Remark 2.2.4 Observe the following:

The inverse of the elementary matrix E_ij is the matrix E_ij itself. That is, E_ijE_ij = I = E_ij E_ij.
Let c≠0. Then the inverse of the elementary matrix E_k(c) is the matrix E_k(1∕c). That is, E_k (c)E_k(1∕c) = I = E_k(1∕c)E_k(c).
Let c≠0. Then the inverse of the elementary matrix E_ij(c) is the matrix E_ij(-c). That is, E_ij (c)E_ij(-c) = I = E_ij(-c)E_ij(c).
That is, all the elementary matrices are invertible and the inverses are also elementary matrices.
Suppose the row-reduced echelon form of the augmented matrix [Ab] is the matrix [Cd]. As row operations correspond to multiplying on the left with elementary matrices, we can find elementary matrices, say E₁,E₂,…,E_k, such that $Ek ⋅Ek-1⋅⋅⋅E2 ⋅E1 ⋅[Ab] = [Cd ].$ That is, the Gauss-Jordan method (or Gauss Elimination method) is equivalent to multiplying by a finite number of elementary matrices on the left to [Ab].

We are now ready to prove a equivalent statements in the study of invertible matrices.

Theorem 2.2.5 Let A be a square matrix of order n. Then the following statements are equivalent.

A is invertible.
The homogeneous system Ax = 0 has only the trivial solution.
The row-reduced echelon form of A is I_n.
A is a product of elementary matrices.

Proof. 1 2

As A is invertible, we have A^-1A = I_n = AA^-1. Let x₀ be a solution of the homogeneous system Ax = 0. Then, Ax₀ = 0 and Thus, we see that 0 is the only solution of the homogeneous system Ax = 0.

2 3

Let x^t = [x₁,x₂,…,x_n]. As 0 is the only solution of the linear system Ax = 0, the final equations are x₁ = 0, x₂ = 0,…,x_n = 0. These equations can be rewritten as

1⋅x1 +0 ⋅x2 + 0⋅x3 + ⋅⋅⋅+ 0 ⋅xn = 0 0⋅x1 +1 ⋅x2 + 0⋅x3 + ⋅⋅⋅+ 0 ⋅xn = 0 0⋅x +0 ⋅x + 1⋅x + ⋅⋅⋅+ 0 ⋅x = 0 1 2 3 n ... = ... 0⋅x1 +0 ⋅x2 + 0⋅x3 + ⋅⋅⋅+ 1 ⋅xn = 0.

That is, the final system of homogeneous system is given by I_n ⋅ x = 0. Or equivalently, the row-reduced echelon form of the augmented matrix [A0] is [I_n0]. That is, the row-reduced echelon form of A is I_n .

3 4

Suppose that the row-reduced echelon form of A is I_n. Then using Remark 2.2.4.4, there exist elementary matrices E₁,E₂,…,E_k such that

E1E2⋅⋅⋅EkA = In.

(2.2.4)

Now, using Remark 2.2.4, the matrix E_j^-1 is an elementary matrix and is the inverse of E_j for 1 ≤ j ≤ k. Therefore, successively multiplying Equation (2.2.4) on the left by E₁^-1,E₂^-1,…,E_k^-1, we get

A = E-k1E -k-11⋅⋅⋅E -21E-1 1

and thus A is a product of elementary matrices.

4 1

Suppose A = E₁E₂ ⋅⋅⋅ E_k; where the E_i’s are elementary matrices. As the elementary matrices are invertible (see Remark 2.2.4) and the product of invertible matrices is also invertible, we get the required result. □

As an immediate consequence of Theorem 2.2.5, we have the following important result.

Theorem 2.2.6 Let A be a square matrix of order n.

Suppose there exists a matrix C such that CA = I_n. Then A^-1 exists.
Suppose there exists a matrix B such that AB = I_n. Then A^-1 exists.

Proof. Suppose there exists a matrix C such that CA = I_n. Let x₀ be a solution of the homogeneous system Ax = 0. Then Ax₀ = 0 and

x0 = In ⋅x0 = (CA )x0 = C (Ax0) = C0 = 0.

That is, the homogeneous system Ax = 0 has only the trivial solution. Hence, using Theorem 2.2.5, the matrix A is invertible.

Using the first part, it is clear that the matrix B in the second part, is invertible. Hence

AB = In = BA.

Thus, A is invertible as well. □

Remark 2.2.7 Theorem 2.2.6 implies the following:

“if we want to show that a square matrix A of order n is invertible, it is enough to show the existence of
1. either a matrix B such that AB = I_n
2. or a matrix C such that CA = I_n.
Let A be an invertible matrix of order n. Suppose there exist elementary matrices E₁,E₂,…,E_k such that E₁E₂E_kA = I_n. Then A^-1 = E₁E₂E_k.

Remark 2.2.7 gives the following method of computing the inverse of a matrix.
Summary: Let A be an n×n matrix. Apply the Gauss-Jordan method to the matrix [AI_n]. Suppose the row-reduced echelon form of the matrix [AI_n] is [BC]. If B = I_n, then A^-1 = C or else A is not invertible.

Example 2.2.8 Find the inverse of the matrix ⌊ ⌋
⌈0 0 1⌉
0 1 1
1 1 1 using the Gauss-Jordan method.
Solution: let us apply the Gauss-Jordan method to the matrix ⌊ | ⌋
0 0 1 |1 0 0
⌈ 0 1 1 |0 1 0 ⌉
1 1 1 |0 0 1 .

Thus, the inverse of the given matrix is ⌊ 0 - 1 1⌋
⌈- 1 1 0⌉

1 0 0 .

Exercise 2.2.9

Find the inverse of the following matrices using the Gauss-Jordan method.
(i), (ii), (iii),(iv).
Which of the following matrices are elementary? $⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ 2 0 1 12 0 0 1 - 1 0 1 0 0 0 0 1 0 0 1 ⌈0 1 0⌉,⌈0 1 0⌉ ,⌈0 1 0⌉ ,⌈ 5 1 0⌉ ,⌈0 1 0⌉,⌈1 0 0⌉ . 0 0 1 0 0 1 0 0 1 0 0 1 1 0 0 0 1 0$
Let A = . Find the elementary matrices E₁,E₂,E₃ and E₄ such that E₄ ⋅ E₃ ⋅ E₂ ⋅ E₁ ⋅ A = I₂.
Let B = . Determine elementary matrices E₁,E₂ and E₃ such that E₃ ⋅E₂ ⋅E₁ ⋅ B = I₃.
In Exercise 2.2.9.3, let C = E₄ ⋅ E₃ ⋅ E₂ ⋅ E₁. Then check that AC = I₂.
In Exercise 2.2.9.4, let C = E₃ ⋅ E₂ ⋅ E₁. Then check that BC = I₃.
Find the inverse of the three matrices given in Example 2.2.3.3.
Show that a triangular matrix A is invertible if and only if each diagonal entry of A is non-zero.
Let A be a 1 × 2 matrix and B be a 2 × 1 matrix having positive entries. Which of BA or AB is invertible? Give reasons.
Let A be an n × m matrix and B be an m × n matrix. Prove that
1. the matrix I -BA is invertible if and only if the matrix I -AB is invertible [Hint: Use Theorem 2.2.5.2].
2. (I - BA)^-1 = I + B(I - AB)^-1A whenever I - AB is invertible.
3. (I - BA)^-1B = B(I - AB)^-1 whenever I - AB is invertible.
4. (A^-1 + B^-1)^-1 = A(A + B)^-1B whenever A,B and A + B are all invertible.

We end this section by giving two more equivalent conditions for a matrix to be invertible.

Theorem 2.2.10 The following statements are equivalent for an n × n matrix A.

A is invertible.
The system Ax = b has a unique solution for every b.
The system Ax = b is consistent for every b.

Proof. 1 2

Observe that x₀ = A^-1b is the unique solution of the system Ax = b.

2 3

The system Ax = b has a solution and hence by definition, the system is consistent.

3 1

For 1 ≤ i ≤ n, define e_i = (0,…,0, ◟1◝◜◞ _{i^{th position}},0,…,0)^t, and consider the linear system Ax = e_i . By assumption, this system has a solution, say x_i, for each i,1 ≤ i ≤ n. Define a matrix B = [x₁,x₂,…,x_n]. That is, the i^th column of B is the solution of the system Ax = e_i. Then

AB = A[x1,x2...,xn] = [Ax1, Ax2...,Axn] = [e1,e2...,en] = In.

Therefore, by Theorem 2.2.6, the matrix A is invertible. □

We now state another important result whose proof is immediate from Theorem 2.2.10 and Theorem 2.2.5 and hence the proof is omitted.

Theorem 2.2.11 Let A be an n × n matrix. Then the two statements given below cannot hold together.

The system Ax = b has a unique solution for every b.
The system Ax = 0 has a non-trivial solution.

Exercise 2.2.12

Let A and B be two square matrices of the same order such that B = PA. Prove that A is invertible if and only if B is invertible.
Let A and B be two m×n matrices. Then prove that the two matrices A,B are row-equivalent if and only if B = PA, where P is product of elementary matrices. When is this P unique?
Let b^t = [1,2,-1,-2]. Suppose A is a 4 × 4 matrix such that the linear system Ax = b has no solution. Mark each of the statements given below as true or false?
1. The homogeneous system Ax = 0 has only the trivial solution.
2. The matrix A is invertible.
3. Let c^t = [-1,-2,1,2]. Then the system Ax = c has no solution.
4. Let B be the row-reduced echelon form of A. Then
  1. the fourth row of B is [0,0,0,0].
  2. the fourth row of B is [0,0,0,1].
  3. the third row of B is necessarily of the form [0,0,0,0].
  4. the third row of B is necessarily of the form [0,0,0,1].
  5. the third row of B is necessarily of the form [0,0,1,α], where α is any real number.

2.3 Rank of a Matrix

In the previous section, we gave a few equivalent conditions for a square matrix to be invertible. We also used the Gauss-Jordan method and the elementary matrices to compute the inverse of a square matrix A. In this section and the subsequent sections, we will mostly be concerned with m × n matrices.

Let A by an m×n matrix. Suppose that C is the row-reduced echelon form of A. Then the matrix C is unique (see Theorem 2.1.30). Hence, we use the matrix C to define the rank of the matrix A.

Definition 2.3.1 (Row Rank of a Matrix) Let C be the row-reduced echelon form of a matrix A. The number of non-zero rows in C is called the row-rank of A.

For a matrix A, we write ‘row-rank (A)’ to denote the row-rank of A. By the very definition, it is clear that row-equivalent matrices have the same row-rank. Thus, the number of non-zero rows in either the row echelon form or the row-reduced echelon form of a matrix are equal. Therefore, we just need to get the row echelon form of the matrix to know its rank.

Example 2.3.2

Determine the row-rank of A = .
Solution: The row-reduced echelon form of A is obtained as follows:
$⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌈1 2 1 1⌉ ⌈1 2 1 1⌉ ⌈1 2 1 1⌉ ⌈1 0 0 1⌉ 2 3 1 2 → 0 - 1 - 1 0 → 0 1 1 0 → 0 1 0 0 . 1 1 2 1 0 - 1 1 0 0 0 2 0 0 0 1 0$
The final matrix has 3 non-zero rows. Thus row-rank(A) = 3. This also follows from the third matrix.
Determine the row-rank of A = .
Solution: row-rank(A) = 2 as one has the following:
$⌊ ⌋ ⌊ ⌋ ⌊ ⌋ 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 ⌈ 2 3 1 2 2⌉ → ⌈0 - 1 - 1 0 0⌉ → ⌈0 1 1 0 0⌉ . 1 1 0 1 1 0 - 1 - 1 0 0 0 0 0 0 0$

The following remark related to the augmented matrix is immediate as computing the rank only involves the row operations (also see Remark 2.1.29).

Remark 2.3.3 Let Ax = b be a linear system with m equations in n unknowns. Then the row-reduced echelon form of A agrees with the first n columns of [Ab], and hence

row- rank(A) ≤ row-rank([Ab ]).

Now, consider an m × n matrix A and an elementary matrix E of order n. Then the product AE corresponds to applying column transformation on the matrix A. Therefore, for each elementary matrix, there is a corresponding column transformation as well. We summarize these ideas as follows.

Definition 2.3.4 The column transformations obtained by right multiplication of elementary matrices are called column operations.

Example 2.3.5 Let A = ⌊ ⌋
1 2 3 1
⌈ 2 0 3 2⌉
3 4 5 3 . Then

⌊ 1 0 0 0⌋ ⌊ ⌋ ⌊1 0 0 - 1⌋ ⌊ ⌋ | 0 0 1 0| 1 3 2 1 |0 1 0 0 | 1 2 3 0 A|⌈ 0 1 0 0|⌉ = ⌈2 3 0 2⌉ and A |⌈0 0 1 0 |⌉ = ⌈2 0 3 0⌉ . 0 0 0 1 3 5 4 3 0 0 0 1 3 4 5 0

Remark 2.3.6 After application of a finite number of elementary column operations (see Definition 2.3.4) to a matrix A, we can obtain a matrix B having the following properties:

The first nonzero entry in each column is 1, called the leading term.
Column(s) containing only 0’s comes after all columns with at least one non-zero entry.
The first non-zero entry (the leading term) in each non-zero column moves down in successive columns.

We define column-rank of A as the number of non-zero columns in B.

It will be proved later that row-rank(A) = column-rank(A). Thus we are led to the following definition.

Definition 2.3.7 The number of non-zero rows in the row-reduced echelon form of a matrix A is called the rank of A, denoted rank(A).

we are now ready to prove a few results associated with the rank of a matrix.

Theorem 2.3.8 Let A be a matrix of rank r. Then there exist a finite number of elementary matrices E₁,E₂,…,E_s and F₁,F₂,…,F_ℓ such that

[ ] Ir 0 E1E2...EsAF1F2 ...Fℓ = 0 0 .

Proof. Let C be the row-reduced echelon matrix of A. As rank(A) = r, the first r rows of C are non-zero rows. So by Theorem 2.1.22, C will have r leading columns, say i₁,i₂,…,i_r. Note that, for 1 ≤ s ≤ r, the i_s^th column will have 1 in the s^th row and zero, elsewhere.

We now apply column operations to the matrix C. Let D be the matrix obtained from C by successively interchanging the s^th and i_s^th column of C for 1 ≤ s ≤ r. Then D has the form [Ir B]
0 0 , where B is a matrix of an appropriate size. As the (1,1) block of D is an identity matrix, the block (1,2) can be made the zero matrix by application of column operations to D. This gives the required result. □

The next result is a corollary of Theorem 2.3.8. It gives the solution set of a homogeneous system Ax = 0. One can also obtain this result as a particular case of Corollary 2.1.23.2 as by definition rank(A) ≤ m, the number of rows of A.

Corollary 2.3.9 Let A be an m × n matrix. Suppose rank(A) = r < n. Then Ax = 0 has infinite number of solutions. In particular, Ax = 0 has a non-trivial solution.

Proof. By Theorem 2.3.8, there exist elementary matrices E₁,…,E_s and F₁,…,F_ℓ such that E₁ E₂ ⋅⋅⋅ E_sAF₁F₂F_ℓ = [ ]
Ir 0
0 0 . Define P = E₁E₂E_s and Q = F₁F₂F_ℓ. Then the matrix PAQ = [Ir 0]
0 0 . As E_i’s for 1 ≤ i ≤ s correspond only to row operations, we get AQ = [C |0 ]
| , where C is a matrix of size m × r. Let Q₁,Q₂,…,Q_n be the columns of the matrix Q. Then check that AQ_i = 0 for i = r + 1,…,n. Hence, the required results follows (use Theorem 2.1.5). □

Exercise 2.3.10

Determine ranks of the coefficient and the augmented matrices that appear in Exercise 2.1.25.2.
Let P and Q be invertible matrices such that the matrix product PAQ is defined. Prove that rank(PAQ) = rank(A).
Let A = and B = . Find P and Q such that B = PAQ.
Let A and B be two matrices. Prove that
1. if A + B is defined, then rank(A + B) ≤ rank(A) + rank(B),
2. if AB is defined, then rank(AB) ≤ rank(A) and rank(AB) ≤ rank(B).
Let A be a matrix of rank r. Then prove that there exists invertible matrices B_i,C_i such that
B₁ A = ,AC₁ = ,B₂AC₂ = and B₃AC₃ = , where the (1,1) block of each matrix is of size r × r. Also, prove that A₁ is an invertible matrix.
Let A be an m × n matrix of rank r. Then prove that A can be written as A = BC, where both B and C have rank r and B is of size m × r and C is of size r × n.
Let A and B be two matrices such that AB is defined and rank(A) = rank(AB). Then prove that A = ABX for some matrix X. Similarly, if BA is defined and rank (A) = rank (BA), then A = Y BA for some matrix Y. [Hint: Choose invertible matrices P,Q satisfying PAQ = , P(AB) = (PAQ)(Q^-1B) = . Now find R an invertible matrix with P(AB)R = . Define X = RQ^-1.]
Suppose the matrices B and C are invertible and the involved partitioned products are defined, then prove that $[ ]- 1 [ ] A B = 0 C-1 . C 0 B -1 - B -1AC- 1$
Suppose A^-1 = B with A = and B = . Also, assume that A₁₁ is invertible and define P = A₂₂ - A₂₁A₁₁^-1A₁₂. Then prove that
1. A is row-equivalent to the matrix ,
2. P is invertible and B = .

We end this section by giving another equivalent condition for a square matrix to be invertible. To do so, we need the following definition.

Definition 2.3.11 A n × n matrix A is said to be of full rank if rank(A) = n.

Theorem 2.3.12 Let A be a square matrix of order n. Then the following statements are equivalent.

A is invertible.
A has full rank.
The row-reduced form of A is I_n.

Proof. 1 2

Let if possible rank(A) = r < n. Then there exists an invertible matrix P (a product of elementary matrices) such that PA = [B1 B2]
0 0 , where B₁ is an r ×r matrix. Since A is invertible, let A^-1 = [C1]
C
2 , where C₁ is an r × n matrix. Then

[ ][ ] [ ] P = P I = P (AA - 1) = (P A)A- 1 = B1 B2 C1 = B1C1 + B2C2 . n 0 0 C2 0

Thus, P has n-r rows consisting of only zeros. Hence, P cannot be invertible. A contradiction. Thus, A is of full rank.

2 3

Suppose A is of full rank. This implies, the row-reduced echelon form of A has all non-zero rows. But A has as many columns as rows and therefore, the last row of the row-reduced echelon form of A is [0, 0, … , 0, 1]. Hence, the row-reduced echelon form of A is I_n.

3 1

Using Theorem 2.2.5.3, the required result follows. □

2.4 Existence of Solution of Ax = b

In Section 2.2, we studied the system of linear equations in which the matrix A was a square matrix. We will now use the rank of a matrix to study the system of linear equations even when A is not a square matrix. Before proceeding with our main result, we give an example for motivation and observations. Based on these observations, we will arrive at a better understanding, related to the existence and uniqueness results for the linear system Ax = b.

Consider a linear system Ax = b. Suppose the application of the Gauss-Jordan method has reduced the augmented matrix [Ab] to

⌊ 1 0 2 - 1 0 0 2 8⌋ || || || 0 1 1 3 0 0 5 1|| [Cd ] = || 0 0 0 0 1 0 - 1 2|| . || 0 0 0 0 0 1 1 4|| | | ⌈ 0 0 0 0 0 0 0 0⌉ 0 0 0 0 0 0 0 0

Then to get the solution set, we observe the following.
Observations:

The number of non-zero rows in C is 4. This number is also equal to the number of non-zero rows in [Cd]. So, there are 4 leading columns/basic variables.
The leading terms appear in columns 1,2,5 and 6. Thus, the respective variables x₁,x₂,x₅ and x₆ are the basic variables.
The remaining variables, x₃,x₄ and x₇ are free variables.

Hence, the solution set is given by

⌊x1⌋ ⌊8- 2x3 + x4 - 2x7⌋ ⌊ 8⌋ ⌊ - 2⌋ ⌊ 1 ⌋ ⌊- 2⌋ ||x2|| ||1- x3 - 3x4 - 5x7|| || 1|| || - 1|| ||- 3|| ||- 5|| ||x3|| || x3 || || 0|| || 1 || || 0 || || 0|| ||x || = || x ||= || 0||+ x || 0 || + x || 1 ||+ x || 0|| , || 4|| || 4 || || || 3|| || 4|| || 7 || || |x5| | 2+ x7 | | 2| | 0 | | 0 | | 1| ⌈x6⌉ ⌈ 4- x7 ⌉ ⌈ 4⌉ ⌈ 0 ⌉ ⌈ 0 ⌉ ⌈- 1⌉ x7 x7 0 0 0 1

where x₃ ,x₄ and x₇ are arbitrary.
Let x₀ = ⌊ ⌋
8
|| 1||
|| 0||
|| 0||
|| ||
|⌈ 2|⌉
4
0

,u₁ =

⌊ ⌋
- 2
||- 1||
|| 1 ||
|| 0 ||
|| ||
|⌈ 0 |⌉
0
0

,u₂ =

⌊ ⌋
1
||- 3||
|| 0 ||
|| 1 ||
|| ||
|⌈ 0 |⌉
0
0

and u₃ =

⌊ ⌋
- 2
||- 5||
|| 0||
|| 0||
|| ||
|⌈ 1|⌉
- 1
1

.
Then it can easily be verified that Cx₀ = d, and for 1 ≤ i ≤ 3, Cu_i = 0. Hence, it follows that Ax₀ = d, and for 1 ≤ i ≤ 3, Au_i = 0.

A similar idea is used in the proof of the next theorem and is omitted. The proof appears on page § as Theorem 3.3.26.

Theorem 2.4.1 (Existence/Non-Existence Result) Consider a linear system Ax = b, where A is an m × n matrix, and x,b are vectors of orders n× 1, and m× 1, respectively. Suppose rank (A) = r and rank([Ab]) = r_a. Then exactly one of the following statement holds:

If r < r_a, the linear system has no solution.
if r_a = r, then the linear system is consistent. Furthermore,
1. if r = n then the solution set contains a unique vector x₀ satisfying Ax₀ = b.
2. if r < n then the solution set has the form ${x0 +k1u1 + k2u2 + ⋅⋅⋅+ kn- run-r : ki ∈ ℝ,1 ≤ i ≤ n - r},$ where Ax₀ = b and Au_i = 0 for 1 ≤ i ≤ n - r.

Remark 2.4.2 Let A be an m × n matrix. Then Theorem 2.4.1 implies that

the linear system Ax = b is consistent if and only if rank(A) = rank([Ab]).
the vectors u_i, for 1 ≤ i ≤ n - r, correspond to each of the free variables.

Exercise 2.4.3 In the introduction, we gave 3 figures (see Figure 2) to show the cases that arise in the Euclidean plane (2 equations in 2 unknowns). It is well known that in the case of Euclidean space (3 equations in 3 unknowns), there

is a figure to indicate the system has a unique solution.
are 4 distinct figures to indicate the system has no solution.
are 3 distinct figures to indicate the system has infinite number of solutions.

Determine all the figures.

2.5 Determinant

In this section, we associate a number with each square matrix. To do so, we start with the following notation. Let A be an n × n matrix. Then for each positive integers α_i’s 1 ≤ i ≤ k and β_j ’s for 1 ≤ j ≤ ℓ, we write A(α₁,…,α_kβ₁,…,β_ℓ) to mean that submatrix of A, that is obtained by deleting the rows corresponding to α_i’s and the columns corresponding to β_j’s of A.

Example 2.5.1 Let A = ⌊ ⌋
1 2 3
⌈1 3 2⌉
2 4 7 . Then A(1|2) = [ ]
1 2
2 7 , A(1|3) = [ ]
1 3
2 4 and A(1, 2|1, 3) = [4].

With the notations as above, we have the following inductive definition of determinant of a matrix. This definition is commonly known as the expansion of the determinant along the first row. The students with a knowledge of symmetric groups/permutations can find the definition of the determinant in Appendix 11.1.15. It is also proved in Appendix that the definition given below does correspond to the expansion of determinant along the first row.

Definition 2.5.2 (Determinant of a Square Matrix) Let A be a square matrix of order n. The determinant of A, denoted det(A) (or |A|) is defined by

( { a,n ( ) if A = [a](n = 1), det(A) = ( ∑ (- 1)1+ja1jdet A(1|j) , otherwise. j=1

Example 2.5.3

Let A = [-2]. Then det(A) = |A| = -2.
Let A = . Then, det(A) = |A| = aA(1|1)- bA(1|2) = ad - bc. For example, if A = then det(A) = = 1 ⋅ 5 - 2 ⋅ 3 = -1.
Let A = . Then,
$det(A ) = |A | = a det(A(1|1))- a det(A(1|2))+ a det(A (1|3)) 11 | | 12| | 1|3 | = a11 ||a22 a23||- a12||a21 a23||+ a13||a21 a22|| |a32 a33| |a31 a33| |a31 a32| = a11(a22a33 - a23a32)- a12(a21a33 - a31a23) +a13(a21a32 - a31a22) (2.5.1)$
Let A = . Then |A| = 1 ⋅ - 2 ⋅ + 3 ⋅ = 4 - 2(3) + 3(1) = 1.

Exercise 2.5.4 Find the determinant of the following matrices.
i) ⌊127 8⌋
|043 2|
|⌈002 3|⌉

000 5 ,ii) ⌊ 3 0 0 1⌋
| 0 2 0 5|
|⌈ 6 - 7 1 0|⌉

3 2 0 6 ,iii) ⌊ ⌋
1 a a2
⌈1 b b2⌉
1 c c2 .

Definition 2.5.5 (Singular, Non-Singular) A matrix A is said to be a singular if det(A) = 0. It is called non-singular if det(A)≠0.

We omit the proof of the next theorem that relates the determinant of a square matrix with row operations. The interested reader is advised to go through Appendix 11.2.

Theorem 2.5.6 Let A be an n × n matrix. If

B is obtained from A by interchanging two rows then det(B) = -det(A),
B is obtained from A by multiplying a row by c then det(B) = cdet(A),
B is obtained from A by replacing the jth row by jth row plus c times the ith row, where i≠j then det(B) = det(A),
all the elements of one row or column of A are 0 then det(A) = 0,
two rows of A are equal then det(A) = 0.
A is a triangular matrix then det(A) is product of diagonal entries.

Since det(I_n) = 1, where I_n is the n×n identity matrix, the following remark gives the determinant of the elementary matrices. The proof is omitted as it is a direct application of Theorem 2.5.6.

Remark 2.5.7 Fix a positive integer n. Then

det(E_ij) = -1, where E_ij corresponds to the interchange of the i^th and the j^th row of I_n.
For c≠0, det(E_k(c)) = c, where E_k(c) is obtained by multiplying the k^th row of I_n by c.
For c≠0, det(E_ij(c)) = 1, where E_ij(c) is obtained by replacing the j^th row of I_n by the j^th row of I_n plus c times the i^th row of I_n.

Remark 2.5.8 Theorem 2.5.6.1 implies that “one can also calculate the determinant by expanding along any row.” Hence, the computation of determinant using the k-th row for 1 ≤ k ≤ n is given by

∑n ( ) det(A) = (- 1)k+jakjdetA (k |j) . j=1

Example 2.5.9

Let A = . Determine det(A).
Solution: Check that

. Thus, using Theorem 2.5.6, det(A) = 2 ⋅ 1 ⋅ 2 ⋅ (-1) = -4.
Let A = . Determine det(A).
Solution: The successive application of row operations R₁(2),R₂₁(-1),R₃₁(-1), R₄₁(-3),R₂₃ and R₃₄(-4) and the application of Theorem 2.5.6 implies $||1 1 3 4|| ||0 2 - 1 2|| det(A) = 2⋅(- 1)⋅|| ||= - 16. ||0 0 - 1 0|| 0 0 0 - 4$ Observe that the row operation R₁(2) gives 2 as the first product and the row operation R₂₃ gives -1 as the second product.

Remark 2.5.10

Let u^t = (u₁,u₂) and v^t = (v₁,v₂) be two vectors in ℝ². Consider the parallelogram on vertices P = (0,0)^t,Q = u,R = u + v and S = v (see Figure 3). Then Area(PQRS) = |u₁ v₂ - u₂v₁|, the absolute value of .

Recall the following: The dot product of u^t = (u₁,u₂) and v^t = (v₁,v₂), denoted u ∙ v, equals u ∙ v = u₁v₁ + u₂v₂, and the length of a vector u, denoted ℓ(u) equals ℓ(u) = . Also, if θ is the angle between u and v then we know that cos(θ) = . Therefore
$∘ --------------- ( -u-∙v--)2 Area(PQRS ) = ℓ(u)ℓ(v)sin(θ) = ℓ(u)ℓ(v) 1- ℓ(u )ℓ(v) ∘-------------------- ∘ ------------- = ℓ(u)2 + ℓ(v)2 - (u ∙v)2 = (u1v2 - u2v1)2 = |u1v2 - u2v1|.$
That is, in ℝ², the determinant is ± times the area of the parallelogram.
Consider Figure 3 again. Let u^t = (u₁,u₂,u₃),v^t = (v₁,v₂,v₃) and w^t = (w₁,w₂,w₃) be three vectors in ℝ³. Then u ∙ v = u₁v₁ + u₂v₂ + u₃v₃ and the cross product of u and v, denoted u × v, equals $u × v = (u2v3 - u3v2,u3v1 - u1v3,u1v2 - u2v1).$ The vector u × v is perpendicular to the plane containing both u and v. Note that if u₃ = v₃ = 0, then we can think of u and v as vectors in the XY -plane and in this case ℓ(u × v) = |u₁v₂ - u₂v₁| = Area(PQRS). Hence, if γ is the angle between the vector w and the vector u × v, then $||w w w || || 1 2 3|| volume (P) = Area(P QRS )⋅height = |w ∙(u × v)| = ± ||u1 u2 u3||. v1 v2 v3$

In general, for any n×n matrix A, it can be proved that |det(A)| is indeed equal to the volume of the n-dimensional parallelepiped. The actual proof is beyond the scope of this book.

Exercise 2.5.11 In each of the questions given below, use Theorem 2.5.6 to arrive at your answer.

Let A = ,B = and C = for some complex numbers α and β. Prove that det(B) = α det(A) and det(C) = det(A).
Let A = and B = . Prove that 3 divides det(A) and det(B) = 0.

2.5.1 Adjoint of a Matrix

Definition 2.5.12 (Minor, Cofactor of a Matrix) The number det (A(i|j)) is called the (i, j)^th minor of A. We write A_ij = det. The (i,j)^th cofactor of A, denoted C_ij, is the number (-1)^i+jA_ij.

Definition 2.5.13 (Adjoint of a Matrix) Let A be an n × n matrix. The matrix B = [b_ij] with b_ij = C_ji, for 1 ≤ i,j ≤ n is called the Adjoint of A, denoted Adj(A).

Example 2.5.14 Let A = ⌊ 1 2 3⌋
⌈ 2 3 1⌉
1 2 2 . Then Adj(A) = ⌊ 4 2 - 7⌋
⌈- 3 - 1 5⌉
1 0 - 1 as

C11 = (- 1)1+1A11 = 4,C21 = (- 1)2+1A21 = 2,...,C33 = (- 1)3+3A33 = - 1.

Theorem 2.5.15 Let A be an n × n matrix. Then

for 1 ≤ i ≤ n, ∑ _j=1ⁿa_ijC_ij = ∑ _j=1ⁿa_ij(-1)^i+jA_ij = det(A),
for i≠ℓ,∑ _j=1ⁿa_ijC_ℓj = ∑ _j=1ⁿa_ij(-1)^ℓ+jA_ℓj = 0, and
A(Adj(A)) = det(A)I_n. Thus,
$wheneverdet(A ) ⁄= 0 one has A -1 =-1-Adj (A ). det(A )$ (2.5.2)

Proof. Part 1: It directly follows from Remark 2.5.8 and the definition of the cofactor.

Part 2: Fix positive integers i,ℓ with 1 ≤ i≠ℓ ≤ n. And let B = [b_ij] be a square matrix whose ℓ^th row equals the i^th row of A and the remaining rows of B are the same as that of A.

Then by construction, the i^th and ℓ^th rows of B are equal. Thus, by Theorem 2.5.6.5, det(B) = 0. As A(ℓ|j) = B(ℓ|j) for 1 ≤ j ≤ n, using Remark 2.5.8, we have

n n ∑ ℓ+j ( ) ∑ ℓ+j ( ) 0 = det(B ) = j=1(- 1) bℓjdetB (ℓ|j) = j=1(- 1) aijdet B(ℓ|j) n n = ∑ (- 1)ℓ+ja det(A (ℓ|j)) = ∑ a C . (2.5.3) j=1 ij j=1 ij ℓj

This completes the proof of Part 2.

Part 3:, Using Equation (2.5.3) and Remark 2.5.8, observe that

[ ] ∑n ∑n { A(Adj(A)) = aik(Adj(A)) = aikCjk = 0, if i ⁄= j, ij k=1 kj k=1 det(A), if i = j.

Thus, A(Adj(A)) = det(A)I_n. Therefore, if det(A)≠0 then A ( )
-1--Adj(A)
det(A)

= I_n. Hence, by Theorem 2.2.6,

A -1 = --1--Adj(A ). det(A)

□

Example 2.5.16 For A = ⌊1 - 1 0⌋
⌈ ⌉
0 1 1
1 2 1 , Adj(A) = ⌊- 1 1 - 1⌋
⌈ ⌉
1 1 - 1
- 1 - 3 1 and det(A) = -2. Thus, by Theorem 2.5.15.3, A^-1 = ⌊ ⌋
1∕2 - 1∕2 1∕2
⌈- 1∕2 - 1∕2 1∕2 ⌉
1∕2 3∕2 - 1∕2 .

The next corollary is a direct consequence of Theorem 2.5.15.3 and hence the proof is omitted.

Corollary 2.5.17 Let A be a non-singular matrix. Then

( ) ∑n { det(A ), if j = k, Adj(A) A = det(A)In and aijCik = i=1 0, if j ⁄= k.

The next result gives another equivalent condition for a square matrix to be invertible.

Theorem 2.5.18 A square matrix A is non-singular if and only if A is invertible.

Proof. Let A be non-singular. Then det(A)≠0 and hence A^-1 = --1--
det(A) Adj(A) as .

Now, let us assume that A is invertible. Then, using Theorem 2.2.5, A = E₁E₂ ⋅⋅⋅ E_k, a product of elementary matrices. Also, by Remark 2.5.7, det(E_i)≠0 for each i,1 ≤ i ≤ k. Thus, by a repeated application of the first three parts of Theorem 2.5.6 gives det(A)≠0. Hence, the required result follows. □

We are now ready to prove a very important result that related the determinant of product of two matrices with their determinants.

Theorem 2.5.19 Let A and B be square matrices of order n. Then

det(AB ) = det(A )det(B ) = det(BA ).

Proof. Step 1. Let A be non-singular. Then by Theorem 2.5.15.3, A is invertible. Hence, using Theorem 2.2.5, A = E₁E₂ ⋅⋅⋅ E_k, a product of elementary matrices. Then a repeated application of the first three parts of Theorem 2.5.6 gives

det(AB ) = det(E1E2 ⋅⋅⋅EkB ) = det(E1) det(E2 ⋅⋅⋅EkB ) = det(E1 )det(E2)det(E3⋅⋅⋅EkB ) = det(E E )det(E )det(E ⋅⋅⋅E B ) 1 2 3 4 k = ... = det(E1E2 ⋅⋅⋅Ek)det(B ) = det(A)det(B).

Thus, if A is non-singular then det(AB) = det(A)det(B). This will be used in the second step.

Step 2. Let A be singular. Then using Theorem 2.5.18 A is not invertible. Hence, there exists an invertible matrix P such that PA = C, where C = [ ]
C1
0 . So, A = P^-1C and therefore

( [ ]) det(AB ) = det((P -1C)B ) = det(P -1(CB )) = det P -1 C1B 0 ( [C1B]) = det(P-1)⋅det 0 as P -1 is non-singular = det(P)⋅0 = 0 = 0 ⋅det(B) = det(A )det(B ).

Thus, the proof of the theorem is complete. □

The next result relates the determinant of a matrix with the determinant of its transpose. As an application of this result, determinant can be computed by expanding along any column as well.

Theorem 2.5.20 Let A be a square matrix. Then det(A) = det(A^t).

Proof. If A is a non-singular, Corollary 2.5.17 gives det(A) = det(A^t).

If A is singular, then by Theorem 2.5.18, A is not invertible. Therefore, A^t is also not invertible (as A^t is invertible implies A^-1 = (A^t)^-1^t)). Thus, using Theorem 2.5.18 again, det(A^t) = 0 = det(A). Hence the required result follows. □

2.5.2 Cramer’s Rule

Let A be a square matrix. Then using Theorem 2.2.10 and Theorem 2.5.18, one has the following result.

Theorem 2.5.21 Let A be a square matrix. Then the following statements are equivalent:

A is invertible.
T he linear system Ax = b has a unique solution for every b.
det(A)≠0.

Thus, Ax = b has a unique solution for every b if and only if det(A)≠0. The next theorem gives a direct method of finding the solution of the linear system Ax = b when det(A)≠0.

Theorem 2.5.22 (Cramer’s Rule) Let A be an n × n matrix. If det(A)≠0 then the unique solution of the linear system Ax = b is

xj = det(Aj), for j = 1,2,...,n, det(A )

where A_j is the matrix obtained from A by replacing the jth column of A by the column vector b.

Proof. Since det(A)≠0, A^-1 = --1---
det(A ) Adj(A). Thus, the linear system Ax = b has the solution x = 1-
det(A) Adj(A)b. Hence x_j, the jth coordinate of x is given by

xj = b1C1j +-b2C2j +-⋅⋅⋅+-bnCnj-= det(Aj). det(A ) det(A )

□

In Theorem 2.5.22 A₁ = ⌊ ⌋
b1 a12 ⋅⋅⋅ a1n
|| b2 a22 ⋅⋅⋅ a2n ||
|⌈ .. .. .. .. |⌉
. . . .
bn an2 ⋅⋅⋅ ann , A₂ = ⌊ ⌋
a11 b1 a13 ⋅⋅⋅ a1n
|| a21 b2 a23 ⋅⋅⋅ a2n||
|⌈ .. .. .. .. ..|⌉
. . . . .
an1 bn an3 ⋅⋅⋅ ann and so on till A_n = ⌊a11 ⋅⋅⋅ a1n-1 b1⌋
|a12 ⋅⋅⋅ a2n-1 b2|
||.. .. .. .. ||
⌈. . . . ⌉
a1n ⋅⋅⋅ ann-1 bn .

Example 2.5.23 Solve Ax = b using Cramer’s rule, where A = ⌊ 1 2 3⌋
⌈ ⌉
2 3 1
1 2 2 and b = ⌊ 1⌋
⌈ ⌉
1
1 .
Solution: Check that det(A) = 1 and x^t = (-1,1,0) as

||1 2 3|| ||1 1 3|| ||1 2 1|| x = ||1 3 1||= - 1,x = ||2 1 1||= 1, and x = ||2 3 1||= 0. 1 || || 2 || || 3 || || 1 2 2 1 1 2 1 2 1

2.6 Miscellaneous Exercises

Exercise 2.6.1

Let A be an orthogonal matrix. Prove that detA = ±1.
Prove that every 2 × 2 matrix A satisfying tr(A) = 0 and det(A) = 0 is a nilpotent matrix.
Let A and B be two non-singular matrices. Are the matrices A+B and A-B non-singular? Justify your answer.
Let A be an n × n matrix. Prove that the following statements are equivalent:
1. A is not invertible.
2. rank(A)≠n.
3. det(A) = 0.
4. A is not row-equivalent to I_n.
5. The homogeneous system Ax = 0 has a non-trivial solution.
6. The system Ax = b is either inconsistent or it is consistent and in this case it has an infinite number of solutions.
7. A is not a product of elementary matrices.
For what value(s) of λ does the following systems have non-trivial solutions? Also, for each value of λ, determine a non-trivial solution.
1. (λ - 2)x + y = 0,x + (λ + 2)y = 0.
2. λx + 3y = 0,(λ + 6)y = 0.
Let x₁,x₂,…,x_n be fixed reals numbers and define A = [a