Chapter 2

MATRIX THEORY

.

Matrices

An m´ n matrix A = (a_ij), 1 £ i £ m, 1 £ j £ n, is an abstraction of a rectangular arrangement of the m´ n entries a_ij into m-rows and n-columns:

.

In general the entries in a matrix could be all kind of objects. If these objects come from a set S , we say that the matrix is over the set S . For definitive results in the sequel we shall mostly confine ourselves to matrices over certain structured sets (e.g., those of real and complex numbers, or polynomials etc.) which seem to us most useful.

The set of all m´ n matrices over a field F is denoted by F ^m´ n , F ^m,n or just F ^mn, if no confusion is caused. Those not interested in a general field F may, with a little loss and a possible ambiguity at places, assume F to be particularized to mean either the set R of real numbers or the set C of complex numbers with the standard operations of addition and multiplication (as well as subtraction and division) defined for them. A matrix over R is called a real matrix and that over C a complex matrix. A general m´ n matrix A is called a rectangular matrix, while if m and n equal, A is termed a square matrix of order n. An m´ 1 matrix is also called an m-component or m-dimensional column vector and a 1´ n matrix is called an n-component or n-dimensional row vector. Here the usage "n-component vector" is to be preferred over "n-dimensional vector" since the latter only refers to a property of the space the vector is coming from and not of the vector itself, whereas the n-components of the vectors are, of course, visibly clear. The set of all n´ 1 column vectors over a field F is simply denoted by F ⁿ (instead of the bulkier notation F ⁿ´ 1 ). The particular case C ⁿ is called the unitary n-space and R ⁿ, the Euclidean n-space. Similarly. we will denote the set of all 1´ n row-vectors over a field F by F ⁽ⁿ⁾. A sub-matrix of a matrix A is a matrix obtained from A by deleting a certain number of rows and columns from A.

PROBLEMS

2. Check if the total number of sub-matrices of an m´ n matrix is the odd number 2^m+n – 2^m – 2ⁿ + 1?

3. If the 3´ 4 matrix A of units of assets of three Stockists is given as per the table:

and a commission agent buys/sells different items in rupees per unit of the items as given in the following 4´ 2 matrix C in the table:

t_i = S ₁£ j£ 4 a_ij (c_j2 – c_j1 ), 1 £ i £ 3.

4. Show the number of p´ q sub-matrices of an m´ n matrix is [m! n!]/[(m-p)!(n-q)!p! q!] = ^mC_p ´ ⁿC_q.

Matrix Addition

If A and B are two m´ n matrices over a field F , their addition or sum matrix A+B is defined as an m´ n matrix C written as C = A + B, whose (i, j)-th element c_ij is given by: c_ij = a_ij + b_ij, 1 £ i £ m, 1 £ j £ n. The difference E = A - B of two matrices A and B is defined similarly (i.e., by: e_ij = a_ij – b_ij , 1 £ i £ m, 1 £ j £ n). Note that a zero matrix (i.e., a matrix with all entries 0) added to, or subtracted from, a matrix does not change it and that this property is enjoyed only by the zero matrix.

PROBLEMS

4. Let {A_k}_k³ 1 denote a sequence of matrices. Discuss what meaning should be ascribed to the writing

B = A₁ + A₂ + ... + A_j-1 + A_j = S ₁£ k£ j A_k?

C = A₁ + A₂ + ... + A_j + ... = S _k³ 1 A_k?

Could you imagine a situations where an infinite sum could be meaningful? Would an infinite sum be meaningful if the field under consideration is not a subfield of C ?

Matrix Multiplication

If A is m´ n and B is n´ p, that is the number of columns of A equals the number of rows in B, their multiplication or product AB is defined as an m´ p matrix C, written C = AB, for which

.

Note that AB is an m´ p matrix and that in order for it to be defined the number of columns in A has to equal the number of rows in B. Moreover, the order in which A and B occur in AB is important.

.

If A = (a_ij ) is an m´ n matrix, the n´ m matrix B defined by b_ij = a_ji is called the transpose of the matrix A and is denoted by A¢ , A^tr or A^t. If A and C are both m´ n we note that both the products A'B and BA' are defined and are respectively n´ n and m´ m matrices.

An n´ n matrix B for which b_ij = 0, if i ¹ j, and b_ii = 1 is called the n´ n identity matrix and is denoted by I_n. When the size n is understood from the context one drops n form I_n and writes it simply as I. Thus the symbol I commonly denotes identity matrices of various sizes. It is clear from the definition of matrix multiplication that IA = A and AI = A for any m´ n A, where the two identity matrices are respectively m´ m and n´ n.

PROBLEMS

2. Verify that the matrix multiplication is associative, i.e., A(BC) = (AB)C, (A l´ m, B m´ n, C n´ p). Construct examples to show that it is not commutative, in general, i.e., AB = BA does not hold for all n´ n A and B. Also prove that the matrix multiplication is both left and right distributive over the matrix addition, i.e., A(B + C) = AB + AC, (A m´ n, B, C n´ p) and (A + B)C = AC + BC, (A, B m´ n, C n´ p).

4. Let e = ad - bc ¹ 0. Let . Compute AB and BA. If x = Ay, show that y = Bx? If F is a matrix and z a vector such that Ay = Fz, find a matrix C such that y = Bz?

5. Find the number of distinct 2x2 matrices A ¹ 0, with entries 0 and 1 only that satisfy A² = 0, where the field F under consideration equals (a) R , (b) C , (c) Z ₂, & (d) Z ₃.

8. If BA = A for all m´ n A, prove that B = I_m and that if AC = A for all m´ n A, then C = I_n.

.

show that A = LU, where b ₁ = b₁, g ₁ = c₁/b ₁; b _j = b_j –a_jg j-1, j = 2, 3, ... , n, and g _j = c_j/b _j, j = 2, 3, ... , n-1, provided that b _j, 1 £ j £ n-1 are all different from zero. Further, show that the problem of solving the system of linear equations Ax = y gets transformed to that of solving the two related systems Lz = y and Ux = z, which, if none of the b _j 's are zero, could be solved as follows:

z₁ = y₁/b ₁, z_j = (y_j – a_jz_j-1)/b _j, j = 2, 3, ... , n; x_n = z_n, x_j = z_j - g _jz_j+1, j = n-1, n-2, ... , 1.

12. If the n´ n matrices A, B commute, prove that the binomial expansion (A+B)^m = S ₀£ k£ m ^mC_kA^m-kB^k, is valid. Construct examples of non-commutative matrices where (a) the expansion is valid, and (b) the expansion is not valid.

16. If A is an n´ n upper triangular matrix, show that Ax = b is solvable for every b iff a_ii ¹ 0, 1 £ i £ n. What happens if A is lower triangular?

Scalar Multiplication

The Product of a matrix A by a scalar t is defined as the matrix C = tA where c_ij = ta_ij, i.e., to get tA, each entry of A is multiplied by the scalar t. An m´ m matrix B is called a scalar matrix if for some scalar c, b_ii = c and b_ij = 0, if i ¹ j. Thus a scalar matrix is a matrix of type cI, where I is an identity matrix. It is then easy to see that cA = (cI)A, i.e., scalar multiplying A by c is equivalent to pre-multiplying A by the scalar matrix cI, where I is m´ m if A is m´ n. Since (tI_m)A = tA = A(tI_n), often "At" is also used denote the scalar multiplication of A by the scalar t, and thus we have At º tA.

Quite often one identifies a scalar s with the 1´ 1 matrix (s); but then sA or As are not to be confused with the matrix products (s)A or A(s), which may not be defined at all. Indeed (s)A is defined iff A is 1´ n and then of course (s)A = sA. Similarly A(s) is defined iff A is m´ 1, and then A(s) = sA.

PROBLEMS

1. Let U denote an n´ n matrix with 1's along the super-diagonal and 0's elsewhere:

.

Compute U², U³, ... , U^n-1, Uⁿ. Hence, if I denotes the n´ n identity matrix (i.e., the matrix whose all diagonal elements are 1 and the off diagonal elements 0) and p = min{m, n-1}, show that

(l I+U)^m = S ₁£ k£ p ^mC_k l ^m-k U^k.

2. Let A be m´ n, x is n´ 1 and b = Ax. Let C_j denote the n´ 1 vector with i-th component as a_ij. C_j is called the j-th column vector of A. Verify that b = S ₁£ j£ n C_jx_j = C₁x₁ + C₂x₂ + ... + C_nx_n = S ₁£ j£ n x_jC_j.

3. Let A be a 3´ 2 matrix. Prove that for whatever 2´ 2 matrix B there exists a 2´ 3 matrix C such that CA = B iff no column vector of A is a scalar multiple of the other.

4. Let A be a 2´ 2 matrix over a field F with ch(F ) ¹ 2. If A has only two distinct entries a and b both occurring twice and a + b ¹ 0, show that there exist two vectors v₁ and v₂ none of which is a scalar multiple of the other such that Av_i = c_iv_i for some scalar c_i, i = 1, 2. Moreover, show that if v ¹ 0 is any vector and c is a scalar such that Av =cv, then c = c₁ or c = c₂ and then: (i) if c₁ ¹ c₂ , v is a scalar multiples of v₁ or v₂ according as c = c₁ or c = c₂ and (ii) if c₁ = c₂ , v is a sum of scalar multiples of v₁ and v₂.

6. Let A =, x, y Î F ², and c Î F . If Ax = cx, prove that cx = 0. If Ax = Ay = 0, show that x₁y₂ = y₁x₂. Arrive at the same conclusions if A = .

7. If f(x) is a polynomial, A is an n´ n, B an n´ m and C an m´ n matrix over a field F and BC = I, the identity matrix show that f(CAB) = C[f(A)]B.

Block-Partitioned Matrices and Block Operations

By drawing horizontal and vertical lines across a matrix we get a partitioning of a matrix into blocks of sub-matrices such that the sub-matrices along the same row block have the same number of rows and those along the same column block have the same number of columns. Given such a configuration of a matrix A, we say that the matrix A has been given in a block-partitioned form or that A is a block-partitioned matrix. Thus if A is partitioned into p-row blocks and q-column blocks, the (i, j)-th block A_ij, being a sub-matrix of A of size p_i´ q_j , we write

If C₁, C₂, ... ,C_j, ... , C_n denote the column vectors of an m´ n matrix A, the column partitioned form of A is as: A = [C₁ | C₂ | … | C_j | … | C_n]. The row partitioned form of A is defined analogously.

Using the block-partitioned forms, the operations of addition, multiplication and scalar multiplication on matrices can be performed en-block. Thus, let A = (A_ij) and B = (B_ij) be two block partitioned matrices. Then, in the respective cases, assuming that sizes of A and B 's are compatible, in the block-partitioned form one has A+B = (A_ij +B_ij), AB = (S _k A_ikB_kj), and a A = (aA_ij), where on the right hand sides is shown the (i, j)-th block of the matrices on the left hand sides. The compatibility in the above refers to the sizes of blocks being such that the sub-matrices A_ij +B_ij and A_ikB_kj make sense. A verification of these is straightforward evaluation.

PROBLEMS

1. Let B and C be real n´ n matrices and b, c, y and z real n´ 1 column vectors. Let A = B + iC, and for1 £ j £ n, a_j = b_j + ic_j, and x_j = y_j + iz_j. Verify that the n´ n complex system of equations Ax = a is equivalent to the 2n´ 2n real system of equations, written in a block partitioned form as:

.

2. If A = diag (A₁₁,A₂₂, ... ,A_kk) is a block-diagonal n´ n matrix where the diagonal blocks A_ii are square matrices and B is another n´ n matrix such that AB = I, the identity matrix, show that also the matrix B has the form diag (B₁₁,B₂₂, ... ,B_kk). Generalize the result for block triangular matrices.

Vector Spaces of Matrices

With respect to the operations (+) (matrix addition) and (.) (scalar multiplication of matrices) the set V = F^{m´ n} of m´ n matrices over a field F has the following properties:

(1) For A, B Î V and c Î F, A + B Î V and cA Î V. [V is closed under (+) and (× )].

(2) A + B = B + A, for A, B Î V.

(3) A + (B + C) = (A + B) + C, for A, B, C Î V.

(4) There is a 0 (the zero matrix) Î V, such that A + 0 = A for every A Î V.

(5) For every A Î V there is a -A (negative of A, i.e., the matrix whose every entry is the negative of the corresponding entry in A) Î V such that A+(-A) = 0.

(6) 1.A = A, where A Î V and 1 is the unity in F.

(7) a(bC) = (ab)C, where a, b Î F and C Î V (associativity with respect to scalar multiplication.

(8) (a+b)C = aC+bC, where a, b Î F and C Î V (distributivity of scalar multiplication over a scalar sum).

(9) a(B + C) = aB + aC, where a Î F and B, C Î V (distributivity of scalar multiplication over a vector sum).

The vector spaces Fⁿ and F⁽ⁿ⁾ of n-componet column and row vectors, respectively, are simply the vector spaces F^{n´ 1} and F^{1´ n} . More generally, in the sequel, a set V is called a vector space over a field F if there exist operations of vector addition + : V ´ V ® V and scalar multiplication • : F ´ V ® V for which (1)-(9) hold. A subset W of a vector space V which is closed under the operations of addition and scalar multiplication (i.e., + : W ´ W ® W and • : F ´ W ® W) is called a subspace of V.

PROBLEMS

1. If W₁ and W₂ are subspaces of F^{m´ n} show that W = W₁ Ç W₂ is also a subspace. Also prove that W₁ È W₂ is a subspace iff one of W₁ and W₂ is contained in the other.

2. Defining W = W₁ + W₂ = {w₁ + w₂ : w_i Î W_i }, where W_i 's are subspaces of F^{m´ n}, show that W is a subspace of F^{m´ n}.

3. Show that the equation (W₁ + W₂ ) Ç W₃ = W₁ Ç W₃ + W₂ Ç W₃ , is not necessarily true if W_i 's are subspaces.

4. Let W₁ and W₂ denote subsets of F^{2´ 2} of matrices of type and , respectively.

(i) Show that W₁ , W₂ , W₁ Ç W₂ and W₁ + W₂ are subspaces of F^{2´ 2}.

(ii) Note that W₁ and W₂ are each described by three parameters (namely x, y, z and a, b, c) and that no two will do. Now find the number of minimal parameters that descibe W₁ Ç W₂ and W₁ + W₂ .

The Standard Inner Product In Rⁿ and C ⁿ

Let K denote any of the fields R or C . Consider the vector space K ⁿ over K . The sum S ₁£ i£ n x_iy_i* = (x,y), where x = (x₁,x₂, ... ,x_n)¢ , and y = (y₁,y₂, ... ,y_n)¢ Î K ⁿ and y* denotes the complex-conjugate of y, is called the standard inner-product in K ⁿ. Note that when K = R , the complex conjugation is not required and we simply have (x,y) = S ₁£ i£ n x_iy_i.

PROBLEMS

1. Verify the following properties of the standard inner product: (i) (x,x) ³ 0 and the equality holds iff x = 0, (ii) (x+y,z) = (x,z)+(y,z), (iii) (cx,y) = c(x,y), (iv) (x,y) = (y,x)* .

2. Show that the complex l minimizing f(l ) = (x-l y,x-l y) is given by l = (x,y)/(y,y). Deduce that (x,y)(y,x) £ (x,x)(y,y). What if we minimize f(l ) with respect to a real l ?

3. Let A be an m´ n matrix, x Î Rⁿ and y Î R^m . If (Ax,y) = 0 for all x and y, show that A = 0, the matrix with all zero entries.

4. If for A = (a_ij), its conjugate transpose or adjoint A* is defined as the matrix whose (i,j)-th entry equals a_ji* , the complex conjugate of the (j,i)-th entry of A, prove that (Ax,y) = (x,A* y).

5. If A is a complex n´ n matrix and A* = A (i.e., A is self-adjoint), show that (i) (Ax,x) is real for all x Î ℂⁿ, (ii) if for some l Î ℂ and 0 ¹ x Î ℂⁿ, Ax = l x, then l Î ℝ and (iii) if Ax = l x and Ay = m y, where l ¹ m and x, y ¹ 0, then (x,y) = 0.

Linear Independence of Matrices

Let A₁, A₂, ... , A_k be m´ n matrices over a field F. We call them linealy-dependent or simply dependent if there exist c₁, c₂, ... , c_k Î F, not all zero, such that c₁ A₁ + c₂ A₂ + ... + c_k A_k = 0, the m´ n zero-matrix. A finite or infinite set of matrices is called linearly dependent or dependent if a finite subset of it is dependent. A set S of matrices (and the members of it) are called linearly-independent if S is not linearly-dependent. It follows that if S is linearly-independent then A₁, A₂, ... , A_k Î S, c₁, c₂, ... , c_k Î F and c₁ A₁ + c₂ A₂ + ... + c_k A_k = 0 imply that c₁ = c₂ = ... = c_k = 0.

Linear dependence or independence of vectors in Fⁿ and F⁽ⁿ⁾ is synonymous with their linear dependence or independence as elements of F^{n´ 1} and F^{1´ n} , respectively. The notion of linear independence in a general vector space is exaclty analogous, but will be taken up only later.

PROBLEMS

1. Find three vectors in R ³ which are linearly dependent but are such that any two of them are linearly independent.

2. Prove that the four vectors (1,0,0), (0,1,0), (0,0,1) and (1,1,1) in R ⁽³⁾ form a linearly dependent set, but that any three of them are linearly dependent.

3. Give an upper bound for the number of elements in a linearly independent subset of (i) F^{m´ n}, (ii) the set of symmetric matrices in F^{n´ n}, (iii) the set of upper triangular matrices in F^{n´ n} and (iv) the set of diagonal matrices in F^{n´ n}. Is the upper bound sharp?

4. For 1 £ i £ m and 1 £ j £ n, let E_ij denote the m´ n matrix whose (i,j)-th entry is 1 and the remaining entries are all zero. Prove that the matrices E_ij are linearly independent.

5. Prove that the row vectors of an n´ n upper triangular matrix A are linearly independent iff a_ii ¹ 0, 1 £ i £ n. Deduce that the column vectors of an n´ n upper triangular matrix A are linearly independent iff a_ii ¹ 0, 1 £ i £ n.

Some Standard Matrices

In the sequel, unless otherwise stated, elements of matrices will be scalars from a general field F or ℝ (real line) or ℂ (complex plane). The square matrix I = (d _ij), where d _ij is the Kronecker-delta

,

is called an identity matrix. (We have come across this matrix earlier.) Obviously IA = A, AI = A, where A is any m´ n matrix, the first I being m´ m and the second n´ n. A matrix all of whose entries are zero is called a zero or a null matrix.

A matrix B is called a left inverse of a matrix A if BA = I, an identity matrix. In this situation A is equivalently called a right inverse of B. Note that if A is m´ n, here, then B is n´ m. If AB = BA = I, B is called an inverse of A (and is written as B = A^-1 ). Here A has to be a square matrix. Later we will see that in this case AB = I Þ BA = I. Moreover, an inverse, if it exists, will be seen to be unique. Also, the symmetry of the definition implies that if B is the inverse of A then A is the inverse of B. A matrix possessing an inverse is called an invertible or a non- singular matrix. If A^-1 does not exist, A is called singular or non-invertible.

A¢ º A^T º A^t , called the transpose of matrix A = (a_ij), is the matrix A¢ = (a_ji), whose (i,j)-th element is the (j,i)-th element of A. Ā, called conjugate of a complex matrix A is the matrix whose (i,j)-th element is the complex conjugate of the (i,j)-th element of A. Thus Ā = (ā_ij). The conjugate-transpose (sometimes, also called the adjoint) of a complex matrix A is the matrix A* º Ā¢ º (A¢ )^-, obtained by conjugating the transpose, or equivalently, transposing the conjugate of the matrix A.

A matrix A is called symmetric if A = A¢ and skew-symmetric if A¢ = -A. A symmetric matrix with real entries is called a real-symmetric matrix. A is called hermitian if A* = A and skew-hermitian if A* = -A. A is called orthogonal if A^-1 = A¢ , i.e. A¢ A = AA¢ = I. An orthogonal matrix with real entries is called real-orthogonal. A matrix is called unitary if A^-1 = A* , i.e. A* A = AA* = I. Clearly, a real Hermitian matrix is symmetric and a real symmetric matrix is hermitian. Also, a real unitary matrix is orthogonal and a real-orthogonal matrix is unitary.

An m´ n A is called sub-unitary if A* A = I. Thus, a square sub-unitary matrix is unitary. Similarly, if A¢ A = I and A is m´ n, it is called sub-orthogonal (for m = n it becomes orthogonal). A sub-orthogonal matrix with real entries is called a real-sub-orthogonal matrix.

A matrix A with real or complex entries is called positive definite if x* Ax º S ₁£ i£ nS 1£ j£ n a_ij (x_i)^-x_j > 0, for every n´ 1 non-zero complex vector x. If x* Ax ³ 0 for all complex n´ 1 vectors x, A is called a positive semidefinite matrix. If -A is p.d. (positive definite), A is called negative definite (n.d) and similarly, if -A is positive semidefinite (p.s.d), A is called negative semidefinite (n.s.d).

Let A be a square n´ n matrix. The trace of A, written Tr A or tr A, is the sum of its diagonal entries: tr A = S ₁£ i£ n a_ii. By changing the order of the double summation, one easily verifies that tr AB = tr BA, where A is m´ n and B is n´ m.

For a square A, (l ,x) is called an eigen-pair, l an eigen-value and x a corresponding eigen-vector of A if Ax = l x, and x ¹ 0, where l Î F, A is n´ n and x is n´ 1.

PROBLEMS

1. Every real n´ n matrix A can be uniquely written as a sum of a real symmetric matrix and a real skew-symmetric matrix.

2. Every complex n´ n matrix A can be uniquely written as a sum of a Hermitian matrix and a skew-Hermitian matrix.

5. If S is an n´ n upper (lower)-triangular matrix (i.e., entries below (above) the diagonal are all zero) and UT = I, then T is an upper (lower)-triangular matrix. Moreover, the set of all upper (lower) triangular matrices is closed with respect to the operations of sums, differences and scalar, as well as, matrix products.

9. Let A be a complex matrix (i.e., with complex entries). Prove that tr(A* A) = 0 iff A = 0. Find an example of a matrix A ¹ 0, for which tr(A²) = 0.

11. Prove that A^*A is p.s.d. for every complex A and it is p.d. if Ax ¹ 0 for every x ¹ 0.

13. If A and B are n´ n matrices, AB = I implies that BA = I. Can you prove it? Construct examples to show that if A is m´ n and B is n´ m and m < n, it is possible that AB = I (the m´ m identity matrix) but that it is impossible that BA = I (the n´ n identity matrix).

14. Prove that a 2´ 2 matrix A = is invertible iff ad-bc ¹ 0, in which case the inverse of A is given by A^-1 = (ad-bc)^-1.

Elementary Row And Column Operations

The elementary row operations (EROs) on an m´ n matrix A are of the following three types:

(ii) Interchanging i-th and j (¹ i)-th rows.

(iii) Adding to i-th row a scalar c times j (¹ i)-th row.

The operations (i)-(iii) may, respectively, be denoted by cR , Ri « R_j and R_i + cR_j. It is easily seen that their effects are reversible (through the inverse elementary row operations c^-1R , R_i « R_j and R_i - cR_j, respectively).

Let A and B be two m´ n matrices. A is said to be row equivalent to B (A ~ B) if A can be obtained from B by performing a finite number of elementary row operations on B. It follows that the row equivalence is an equivalence relation on F^{m´ n} (i.e., A ~ A, A ~ B Þ B ~ A and A ~ B and B ~ C Þ A ~ C).

A motivation for studying elementary row operations comes from systematizing methods for solving a system of linear equations and related questions. Consider, for instance the problem of determining when two m´ n consistent systems Ax = b and Cx = d are equivalent. A consistent system means that it

Now, starting with a system Ax = b if we apply a succession of the following three types of operations: (1) multiplying both sides of the i-th equation by a non-zero scalar c; (2) interchanging i-th and j (¹ i)-th equations; and (3) adding to i-th equation a scalar c times j (¹ i)-th equation, on the system we get another equivalent system. This is because all these operations are reversible and so if x satisfies the original system it satisfies the transformed one and vice versa. Note the similarity of these operations with the corresponding elementary row operations. Now the interesting result in this direction is the following converse: "Two consistent m´ n systems are equivalent only if one can be obtained from the other in this fashion, i.e., by a succession of the above three types of operations."

Now, suppose Ax = b is an n´ n system possessing a unique solution, given by x_i = d_i, 1 £ i £ n, say. But this writing of the solution again constitutes a system of linear equations of the form Cx = d, with C as the identity matrix. Hence by the above equivalence it follows that the solution can indeed be obtained simply by an appropriate succession of the operations of type (1)-(3). This idea of Gauss leads us to the well-known "elimination method" for solving Ax = b : Use one of the equations to eliminate x₁ from the remaining n-1 equations. Use one of the n-1 equations to eliminate x₂ from the remaining n-2 equations, and so on till you eliminate x_n-1 from the remaining 1 equation which would then contain only x_n . This process is called forward elimination. The n-equations that you have after the forward elimination, are of type Ux = v, where U is an upper triangular matrix. Its solution can be found by the so-called back substitution, which consists in determining x_n from the last equation, substituting for x_n and determining x_n-1 from the (n-1)-th equation, substituting for x_n and x_n-1 and determining x_n-2 from the (n-2)-th equation, and so on till finally substituting for x_n, x_n-1, x_n-2, ... , x₃, x₂ and determining x₁ from the first equation.

One more point: The m´ n system Ax = b is characterized by the matrix A of the system and the right hand vector b. If we construct the m´ (n+1) matrix [A | b], whose first n columns are the columns of the matrix A and the last column is a copy of the vector b, the matrix [A | b] contains all information regarding the system Ax = b excepting for the dummy notation for the vector x, which is of no mathematical consequence anyway. This matrix [A | b] is called the augmented matrix of the system Ax = b. Using the notion of the augmented matrix, we see that if Ax = b is transformed into Cx = d by a succession of the operations (1)-(3), the corresponding operations (i)-(iii) applied on [A | b] convert it to [C | d]. That is why for studying a system Ax = b of equations, we could confine our attention to the augmented matrix [A | b] and the elementary row operations (i)-(iii). The studies subsequently reveal as to how to deal with the inconsistent systems, or the systems that do not possess a unique solution. For the present, we give the following definition: Two m´ n systems (consistent or not) Ax = b and Cx = d are called equivalent if one can be obtained from the other by a finite sequence of operations of type (1)-(3), or equivalently, if [A | b] and [C | d] can be obtained from each other by a succession of elementary row operations.

Let A be m´ n. Each of the above mentioned three elementary row operations (i)-(iii) on A corresponds to premultiplication of A by an m´ m matrix, obtainable by performing the same operation on an m´ m identity matrix. The respective pre-multiplying matrices for (i)-(iii) are thus:

.

In (i)-(iii) the word 'row' changed to 'column' results in the elementary column operations (ECOs). These in turn correspond to post multiplication by n´ n matrices:

.

PROBLEMS

2. For what choice of the parameter a are the following systems of linear equations over the field R consistent:

(a) x₁ + x₂ = 10, (b) x₁ + x₂ = 10, (c) a x₁ + a x₂ = 10,

a x₁ + x₂ = 20. a x₁ + a x₂ = 20. a x₁ + a x₂ = 20.

a x₁ + x₂ + x₃ = 1. a x₁ - x₂ + x₃ = 1.

3. Devise an algorithm (a general strategy, or procedure) for expressing (a) a non-singular n´ n matrix A and (b) its inverse A^-1, as products of elementary matrices. The algorithm should fail iff A is singular. Practise the algorithm on the following matrices:

Row-Reduced Echelon Form

Theorem. Let A be m´ n. Then there exist non-singular m´ m B and n´ n C such that BA is in row-reduced echelon form and AC is in column-reduced echelon form.

Theorem (Unicity of the row-reduced echelon form). Let A be an m´ n matrix over a field. If B and C are non-singular and BA and CA are in row-reduced echelon forms, then BA = CA.

Proof. The proof is by induction on m. When m = 1 the result is obvious. Thus assume the result for (m-1)´ n matrices. Let E = BA and F = CA. Since B and C are non-singular and hence products of elementary matrices, each row of E can be obtained as a linear combination of rows of F and conversely. If E = 0, obviously F = 0 and conversely. If E ¹ 0, F ¹ 0, and let p denote the number of the column in E containing the leading unity of the first row and let let q denote the same for F. If p < q, the columns 1 to q-1 in F are zero. In particular the p-th column of F is zero and hence the first row of E can not be obtained from F by elementary row operations as the p-th column entry of the first row of E is non-zero. Similarly q < p is equally false and so p = q.

Thus, if E₁ and F₁ denote the matrices obtained from E and F, respectively, by deleting their first rows, then E₁ and F₁ are row-equivalent row-reduced echelon forms and hence, by the induction hypothesis for (m-1)´ n matrices, are equal. In view of this the first rows of E and F are also to be the same, since no contribution can come from second onward rows of F while we are writing the first row of E as a linear combinations of the rows of F. Thus the result for m´ n matrices follows and the induction is complete. #

PROBLEMS

3. Describe explicitly the possible forms of all 2´ 2 and 3´ 3 row-reduced echelon matrices. Do these forms depend on the field F under consideration?

x₁ + a x₂ -5x₃ - 2x₄ = 3,

has no solution iff a = 7. If a ¹ 7, find the general solution?

9. If A is an m´ n matrix over a field F, prove that there exists an n´ m matrix B such that x = Bb is a solution of Ax = b, whenever b is such that the system Ax = b is consistent.

11. For a square matrix A over a field F, the following statements are equivalent:

13. Prove that there are exactly two 2´ 2 complex row-reduced echelon matrices the sum of all the four entries of which is 0.

17. If , prove that Ax = l x is a consistent system iff l = 1, or 2, and find all solutions of the systems Ax = x and Ax = 2x.

20. Find all solutions of the system of equations Ax = 0, where , when: (i) A = 0, (ii) A ¹ 0, but ad - bc = 0 and (iii) ad - bc ¹ 0. [The quantity (ad-bc) is known as the determinant of the 2´ 2 A.]