UNIT I System of Linear Equations

Matrices

Definition

A matrix is an arrangement of m \times n elements in m rows and n columns. It is represented as:

A = \begin{bmatrix} a{11} & a{12} & a{13} & \cdots & a{1n} \ a{21} & a{22} & a{23} & & a{2n} \ \vdots & & \ddots & & \vdots \ a{m1} & a{m2} & a{m3} & \ldots & a{mn} \end{bmatrix}

Types of Matrices

Row Matrix

A row matrix (or row vector) is a matrix with one row:

r = \begin{bmatrix} r1 & r2 & r3 & \cdots & rn \end{bmatrix}

Column Matrix

A column matrix (or column vector) is a matrix with only one column:

c = \begin{bmatrix} c1 \ c2 \ \vdots \ c_m \end{bmatrix}

Square Matrix

A square matrix has equal row and column dimensions (m = n).

Diagonal Matrix

A scalar matrix in which all non-diagonal elements are zero.

Unit Matrix

A diagonal matrix in which all diagonal elements are one. Also known as Identity Matrix

Identity Matrix

A square matrix with 1s on the main diagonal and 0s elsewhere:

I = \begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 1 \end{bmatrix}

Upper Triangular Matrix

A matrix where all elements below the main diagonal are zero.

Lower Triangular Matrix

A matrix where all elements above the main diagonal are zero.

Singular Matrix

A square matrix A is singular if its determinant is 0:

|A| = 0

Non-Singular Matrix

A square matrix A is non-singular if its determinant is not 0:

|A| \neq 0

Symmetric Matrix

A square matrix A is symmetric if it equals its transpose:

A = A^T

Skew-Symmetric Matrix

A square matrix A is skew-symmetric if it equals the negative of its transpose:

A = -A^T

Orthogonal Matrix

A square matrix A is orthogonal if:

AA^T = A^T A = I

Algebra of Matrices

Matrix Equality

Two matrices A and B (of the same size m \times n) are equal if and only if all their corresponding elements are equal:

A = B \iff a{ij} = b{ij} \quad \text{for } i = 1,\ldots,m; \quad j = 1,\ldots,n

Matrix Addition

If A and B are two matrices of the same size, their sum is:

A + B = \begin{bmatrix} a{11} & a{12} & \cdots & a{1n} \ a{21} & a{22} & & a{2n} \ \vdots & & \ddots & \vdots \ a{m1} & a{m2} & \ldots & a{mn} \end{bmatrix} + \begin{bmatrix} b{11} & b{12} & \cdots & b{1n} \ b{21} & b{22} & & b{2n} \ \vdots & & \ddots & \vdots \ b{m1} & b{m2} & \ldots & b{mn} \end{bmatrix} = \begin{bmatrix} a{11} + b{11} & a{12} + b{12} & \cdots & a{1n} + b{1n} \ a{21} + b{21} & a{22} + b{22} & & a{2n} + b{2n} \ \vdots & & \ddots & \vdots \ a{m1} + b{m1} & a{m2} + b{m2} & \ldots & a{mn} + b{mn} \end{bmatrix}

Scalar Multiplication

Multiplication of a matrix A by a scalar \alpha:

\alpha A = \alpha \begin{bmatrix} a{11} & a{12} & \cdots & a{1n} \ a{21} & a{22} & & a{2n} \ \vdots & & \ddots & \vdots \ a{m1} & a{m2} & \ldots & a{mn} \end{bmatrix} = \begin{bmatrix} \alpha a{11} & \alpha a{12} & \cdots & \alpha a{1n} \ \alpha a{21} & \alpha a{22} & & \alpha a{2n} \ \vdots & & \ddots & \vdots \ \alpha a{m1} & \alpha a{m2} & \ldots & \alpha a{mn} \end{bmatrix}

Matrix Multiplication

The product of two matrices A and B is defined only if the number of columns of A is equal to the number of rows of B. If A is (m \times p) and B is (p \times n), the product is an (m \times n) matrix C:

C{m \times n} = A{m \times p} B_{p \times n}

C = AB = \begin{bmatrix} a{11} & a{12} & \cdots & a{1p} \ a{21} & a{22} & & a{1p} \ \vdots & & \ddots & \vdots \ a{m1} & a{m2} & \ldots & a{mp} \end{bmatrix} \begin{bmatrix} b{11} & b{12} & \cdots & b{1n} \ b{21} & b{22} & & b{1n} \ \vdots & & \ddots & \vdots \ b{p1} & b{p2} & \ldots & b{pn} \end{bmatrix} = \begin{bmatrix} a{11}b{11} + \cdots + a{1p}b{p1} & a{11}b{12} + \cdots + a{1p}b{p2} & \cdots & a{11}b{1n} + \cdots + a{1p}b{pn} \ a{21}b{11} + \cdots + a{2p}b{p1} & a{21}b{12} + \cdots + a{2p}b{p2} & & a{21}b{1n} + \cdots + a{2p}b{pn} \ \vdots & & \ddots & \vdots \ a{m1}b{11} + \cdots + a{mp}b{p1} & a{m1}b{12} + \cdots + a{mp}b{p2} & \ldots & a{m1}b{1n} + \cdots + a{mp}b{pn} \end{bmatrix}

Matrix Inverse

If A is an (n \times n) non-singular square matrix and there is a matrix B with the property that AB = I. Then B is defined to be the inverse of A and is denoted A^{-1}.

Inverse by Adjoint Method

A^{-1} = \frac{1}{|A|} adj(A)

where adj(A) is the transpose of the cofactor matrix.

Elementary Transformations

The following three types of transformations, performed on any non-zero matrix A, are called elementary transformations:

1. The interchange of the i^{th} and j^{th} row denoted by R{ij} (same for column i.e. C{ij})

2. The multiplication of each element of i^{th} row by non zero scalar k is denoted by kR_i

3. Multiplication of each element of j^{th} row by scalar k and adding to the corresponding element of i^{th} row is denoted by (Ri + kRj).

Elementary Matrix

A matrix obtained by applying a single elementary row or column transformation on an identity matrix is called an Elementary Matrix.

• Every Elementary Matrix is invertible, and inverse of an elementary matrix is an elementary matrix.

• Elementary row transformation corresponds to left multiplication by corresponding elementary matrix.

• Elementary column transformation corresponds to right multiplication by corresponding elementary matrix.

Theorem: Every non-singular matrix can be expressed as a product of elementary matrices.

Examples of Elementary Matrices

a. E1 = \begin{bmatrix} 0 & 1 & 0 \ 1 & 0 & 0 \ 0 & 0 & 1 \end{bmatrix} obtained by R1 \leftrightarrow R2 b. E2 = \begin{bmatrix} 0 & 1 & 0 \ 1 & -1 & 0 \ 0 & 0 & 1 \end{bmatrix} obtained by R2 - R1
c. E3 = \begin{bmatrix} 1 & 0 \ 2 & 1 \end{bmatrix} obtained by R2 + 2R_1

Minor

The minor of an element of matrix A is a determinant obtained by omitting the row and the column in which the element is present.

Example:

A = \begin{bmatrix} a{11} & a{12} & a{13} \ a{21} & a{22} & a{23} \ a{31} & a{32} & a_{33} \end{bmatrix}

Minor of a{11} = M{11} = \begin{vmatrix} a{22} & a{23} \ a{32} & a{33} \end{vmatrix}

Minor of a{23} = M{23} = \begin{vmatrix} a{11} & a{12} \ a{31} & a{32} \end{vmatrix}

Minor of a{32} = M{32} = \begin{vmatrix} a{11} & a{13} \ a{21} & a{23} \end{vmatrix}

Rank of a Matrix

The matrix A is said to be of rank r if

1. There exists at least one minor of the order r which is not equal to zero.

2. Every minor of the order higher than r is equal to zero.

The rank of matrix A is the maximum order of its non-vanishing minor. It is denoted as \rho(A) = r

Examples

1. A = \begin{bmatrix} 1 & 1 & 1 \ 2 & 2 & 2 \ 3 & 3 & 3 \end{bmatrix}

   Since |A| = 0 (minor of order 3), the rank cannot be 3. Similarly, it cannot be 2. Hence, rank is 1 for this matrix.

2. A = \begin{bmatrix} 1 & 0 & 0 \ 0 & 1 & 0 \ 0 & 0 & 1 \end{bmatrix}

   Since |A| \neq 0, the rank is 3.

Properties of Rank of a Matrix

i. Rank of Null Matrix is zero.
ii. \rho(In) = n where In = unit matrix of order n.
iii. Let A be matrix of order m \times n, then \rho(A{m \times n}) \leq min(m, n). iv. \rho(A{n \times n}) = n if |A| \neq 0; < n if |A| = 0
v. If \rho(A) = m and \rho(B) = n then \rho(AB) \leq min(m, n)
vi. If A{m \times 1} is a non-zero column matrix and B{1 \times n} is a non-zero row matrix then \rho(AB) = 1
vii. \rho(A + B) \leq \rho(A) + \rho(B)
viii. \rho(A^T) = \rho(A)

Examples

1. A = \begin{bmatrix} 1 & 2 & 3 \ 2 & 3 & 1 \ 3 & 1 & 2 \end{bmatrix} \quad [\rho(A) = 3]

2. A = \begin{bmatrix} 1 & 1 & 1 \ 2 & 2 & 2 \ 3 & 3 & 3 \end{bmatrix} \quad [\rho(A) = 1]

3. A = \begin{bmatrix} 1 & 1 & 1 \ 1 & 1 & 1 \ 1 & 1 & 1 \end{bmatrix} \quad [\rho(A) = 1]

4. A = \begin{bmatrix} 0 & 1 & 0 \ 0 & 0 & 1 \ 1 & 0 & 0 \end{bmatrix} \quad [\rho(A) = 3]

Echelon Form or Row Echelon Form

Given matrix is said to be in echelon form if it satisfies the following properties:

a) Zero row of matrix (if any) occurs at the bottom of the matrix.
b) The first nonzero number from the left of a nonzero row is 1. This is called leading 1.
c) For two successive (consecutive) nonzero rows, the leading 1 of the upper row appears to the left of the leading 1 of the lower row.

Note: Rank of the matrix is equal to the number of non-zero rows (which are linearly independent) in its echelon form.

Pivot Elements

Leading entry - First non-zero element in a row called as leading entry or pivot element.

Example:

\begin{bmatrix} 1 & 2 & 3 & 5 & -7 \ 0 & 0 & 1 & -2 & 5 \ 0 & 0 & 0 & 1 & -2 \ 0 & 0 & 0 & 0 & 0 \end{bmatrix}

Questions

Q 1] Reduce the following matrix to its Echelon Form and hence find its rank.

1. A = \begin{bmatrix} 4 & 2 & -1 & 2 \ 1 & -1 & 2 & 1 \ 2 & 2 & -2 & 0 \end{bmatrix} \quad ans: \rho(A) = 3

2. A = \begin{bmatrix} 1 & 2 & -2 & 3 \ 2 & 5 & -4 & 6 \ -1 & -3 & 2 & -2 \ 2 & 4 & -1 & 6 \end{bmatrix} \quad ans: \rho(A) = 4

3. A = \begin{bmatrix} 2 & -2 & 0 & 6 \ 4 & 2 & 0 & 2 \ 1 & -1 & 0 & 3 \ 1 & -2 & 1 & 2 \end{bmatrix} \quad ans: \rho(A) = 3

4. A = \begin{bmatrix} 0 & 1 & -3 & -1 \ 1 & 0 & 1 & 1 \ 3 & 1 & 0 & 2 \ 1 & 1 & -2 & 0 \end{bmatrix} \quad ans: \rho(A) = 2

5. A = \begin{bmatrix} 4 & 2 & -1 & 2 \ 1 & -1 & 2 & 1 \ 2 & 2 & -2 & 0 \end{bmatrix} \quad ans: \rho(A) = 3

6. A = \begin{bmatrix} 1 & 2 & -1 & 3 \ 3 & 4 & 0 & -1 \ -1 & 0 & -2 & 7 \end{bmatrix} \quad ans: \rho(A) = 2

7. A = \begin{bmatrix} 1 & 5 & 7 \ 2 & 10 & 14 \ 3 & 15 & 21 \end{bmatrix} \quad ans: \rho(A) = 1

8. A = \begin{bmatrix} 0 & 1 & 0 & 0 \ 0 & 0 & 1 & 0 \ 0 & 0 & 2 & 0 \ 0 & 0 & 0 & 0 \end{bmatrix} \quad ans: \rho(A) = 2

9. A = \begin{bmatrix} -2 & 2 & -1 \ 0 & 3 & 3 \ 1 & -4 & 2 \ 2 & -3 & 2 \end{bmatrix} \quad ans: \rho(A) = 3

10. A = \begin{bmatrix} 4 & -3 & -4 \ -4 & 2 & 1 \ -1 & -3 & 1 \ -2 & -4 & -4 \end{bmatrix} \quad ans: \rho(A) = 3

11. A = \begin{bmatrix} -4 & 1 & 4 \ 3 & 4 & -3 \end{bmatrix} \quad ans: \rho(A) = 2

12. A = \begin{bmatrix} -4 & -2 \ -2 & -1 \ -2 & -3 \ 0 & 0 \end{bmatrix} \quad ans: \rho(A) = 2

Non-Homogeneous System of Equations

AX = B where B is non-zero is called Non-Homogeneous system of equation.

a{11}x1 + a{12}x2 + a{13}x3 + \cdots + a{1n}xn = b1 a{21}x1 + a{22}x2 + a{23}x3 + \cdots + a{2n}xn = b2
\vdots
a{m1}x1 + a{m2}x2 + a{m3}x3 + \cdots + a{mn}xn = b_m

The matrix form of the system is

\begin{bmatrix} a{11} & a{12} & \cdots & a{1n} \ a{21} & a{22} & \cdots & a{2n} \ \vdots & \vdots & \vdots & \vdots \ a{m1} & a{m2} & \cdots & a{mn} \end{bmatrix} \begin{bmatrix} x1 \ x2 \ \vdots \ xn \end{bmatrix} = \begin{bmatrix} b1 \ b2 \ \vdots \ b_m \end{bmatrix}

i.e., AX=B where

A is called the coefficient matrix,
X is called the matrix of variables
B is called the matrix of constants.

Augmented Matrix:

If AX=B is a system of m equations in n variables (unknowns) then the matrix [A|B]is called augmented matrix and is written as

[A|B] = \begin{bmatrix} a{11} & a{12} & \cdots & a{1n} & | & b1 \ a{21} & a{22} & \cdots & a{2n} & | & b2 \ \vdots & \vdots & \cdots & \vdots & | & \vdots \ a{m1} & a{m2} & \cdots & a{mn} & | & bm \end{bmatrix}

Consistent system: System AX = B is said to be consistent iff AX = B has solution

Inconsistent System: System AX = B is said to be inconsistent iff AX = B has no solution

Solving AX = B:

Conditions for Solutions

• If \rho(A) = \rho([A|B]) = n (Number of unknowns): The system is consistent and has a unique solution.

• If \rho(A) = \rho([A|B]) = r < n (Number of unknowns): The system is consistent and has infinitely many solutions (n-r free parameter solutions).

• If \rho(A) \neq \rho([A|B]): The system has no solution.

Solving Consistent Systems

If the given system is consistent, rewrite equations from Echelon form. By using back substitution, we obtain the solution.

Problems

Test for consistency of the following system of equations and if consistent then solve the following equations;

1. 3x + y + 2z = 3; 2x - 3y - z = -3; x + 2y + z = 4

   Ans: x = 1, y = 2, z = -1

2. 5x + 3y + 7z = 4; 3x + 26y + 2z = 9; 7x + 2y + 10z = 5

   Ans: x = \frac{7-16t}{11}, y = \frac{3+t}{11}, z = t

3. 2x + 6y + 11 = 0; 6x + 20y - 6z + 3 = 0; 6y - 18z + 1 = 0

   Ans: system is inconsistent

4. x + 2y + 2z = 1; 2x + 2y + 3z = 3; x - y + 3z = 5

   Ans: x = 1, y = -1, z = 1

5. 2x + z = 4; x - 2y + 2z = 7; 3x + 2y = 1

   Ans: x = \frac{2 - t}{2}, y = \frac{-5}{2} + \frac{3t}{4}, z = t

6. 4x - 2y + 6z = 8; x + y - 3z = -1; 15x - 3y + 9z = 21

   Ans: x = 1, y = 3t - 2, z = t

7. x + y + z = 4; 2x + 5y - 2z = 3;

   Ans: x = \frac{17-7t}{3}, y = \frac{-5+4t}{3}, z = t

8. 2x + 3y + 4z = 11; x + 5y + 7z = 15; 3x + 11y + 13z = 25

   Ans: x = 2, y = -2, z = 4

Problems

Q.1) Investigate the values of \lambda and \mu so that the equations:

2x + 3y + 5z = 9; 7x + 3y - 2z = 8; 2x + 3y + \lambda z = \mu

have

(i) no solution (ii) a unique solution (iii) an infinite number of solutions.

Q.2) Test for consistency and if consistent, solve the following system of equations:

2x - y = 2
x + 2y + z = 2
4x - 7y - 5z = 2

Q.3) For what values of k the equations:

x + y + z = 1; 2x + y + 4z = k; 4x + y + 10z = k^2

have infinite number of solutions? Hence find solutions.

Q. 4) Show that the system :

3x + 4y + 5z = \alpha; 4x + 5y + 6z = \beta; 5x + 6y + 7z = \gamma

is consistent only when \alpha, \beta, \gamma are in arithmetic progression.

Homogeneous System of Equations

The system AX=B is called a homogeneous system if the matrix B is a null matrix.
It is denoted by AX=Z (AX=0)

Here A is the coefficient matrix, X is the variable matrix, and Z is the null matrix.
Note: Homogeneous system is always consistent. i.e., \rho(A)=\rho(A,Z)
always
The system of equation is given by

a{11}x1 + a{12}x2 + a{13}x3 + \cdots + a{1n}xn = 0
a{21}x1 + a{22}x2 + a{23}x3 + \cdots + a{2n}xn = 0
\vdots
a{m1}x1 + a{m2}x2 + a{m3}x3 + \cdots + a{mn}xn = 0

Solutions of Homogeneous Systems

• If \rho(A)=\rho(A,Z) = Number of variables, then the system has a trivial solution ( x = 0, y = 0, z = 0)

• If \rho(A)=\rho(A,Z) < Number of variables, then the system has non-trivial solutions.

• Consider the system of equations AX=0 where A is the square matrix then
  i. If |A| =0, then system possesses a nontrivial solution. The solution can be obtained by rank method. ii. If |A| \neq 0, then the system possesses only trivial solution.

Problems

Q. 1) Solve: x + 2y + 2z = 0; 2x + 2y + 3z = 0; x - y + 3z = 0

Q. 2) Show that the system of equations,
x1 + 2x2 + 3x3 = \lambda x1; 3x1 + x2 + 2x3 = \lambda x2; 2x1 + 3x2 + x3 = \lambda x3
can possess a non-trivial solution only if \lambda = 6. Obtain general solution for real values of \lambda.

Q.3) Show that the equations,
ax + by + cz = 0; bx + cy + az = 0; cx + ay + bz = 0
has a non-trivial solutions only if a + b + c = 0 or a = b = c

Q.4) Solve: 5x + 3y + 7z = 0; 3x + 26y + 2z = 0; 7x + 2y + 10z = 0

Q.5) Solve: 2x + z = 0; x - 2y + 2z = 0; 3x + 2y = 0

System of Equations Summary

System of Equations (AX = B)

• Homogeneous system AX = 0 (B = 0)

  • Always Consistent \rho(A│B) = \rho(A)

    • Unique Solution (always trivial solution) (X = 0)

      • \rho(A)=n

    • Non-trivial solutions

      • \rho(A) < n

• Non-homogenous System AX = B (B≠ 0)

  • Consistent \rho(A│B) = \rho(A)

    • Unique Solution \rho(A)=n

    • Infinite solutions \rho(A) < n

  • Inconsistent \rho(A│B) ≠ \rho(A)

Gauss Jordan Elimination Method

Gauss –Jordan elimination method is a numerical method that is used to solve systems of linear equations.
It involves performing elementary row operations on an augmented matrix to transform it to reduced row echelon form.
Example of reduced row echelon form

a) \begin{bmatrix} 1 & 0 & 0 \ 0 & 1 & 3 \ 0 & 0 & 0 \end{bmatrix}
b) \begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 2 \ 0 & 0 & 1 & 0 \end{bmatrix}
c) \begin{bmatrix} 1 & 0 & 4 \ 0 & 1 & 5 \end{bmatrix}

Steps to solve the system of equations by Gauss-Jordan elimination

Step 1 : Write the augmented matrix of the linear system.

Step 2 : Use row operations to reduce the augmented matrix to reduced row echelon Form.

Step 3 : Interpret the final matrix as a linear system

Step 4 : Use back substitution and write the solution.

Examples on Gauss Jordan Method

Solve the following system of equations using the Gauss Jordan Elimination method.

Q.1 x + y + z = 5
2x + 3y + 5z = 8
4x + 5z = 2

Solution:

Step 1: Write the system in matrix form

\begin{bmatrix} 1 & 1 & 1 \ 2 & 3 & 5 \ 4 & 0 & 5 \end{bmatrix} \begin{bmatrix} x \ y \ z \end{bmatrix} = \begin{bmatrix} 5 \ 8 \ 2 \end{bmatrix}

AX = B

Step 2: Write the augmented matrix

[A:B] = \begin{bmatrix} 1 & 1 & 1 & | & 5 \ 2 & 3 & 5 & | & 8 \ 4 & 0 & 5 & | & 2 \end{bmatrix}

Step 3: Reduce the above matrix to row echelon form by elementary row transformation

R2 - 2R1 & R3 - 4R1

[A:B] \sim \begin{bmatrix} 1 & 1 & 1 & | & 5 \ 0 & 1 & 3 & | & -2 \ 0 & -4 & 1 & | & -18 \end{bmatrix}

R3 + 4R2

[A:B] \sim \begin{bmatrix} 1 & 1 & 1 & | & 5 \ 0 & 1 & 3 & | & -2 \ 0 & 0 & 13 & | & -26 \end{bmatrix}

(\frac{1}{13})R_3

[A:B] \sim \begin{bmatrix} 1 & 1 & 1 & | & 5 \ 0 & 1 & 3 & | & -2 \ 0 & 0 & 1 & | & -2 \end{bmatrix}

R2 - 3R3 & R1 - R3

[A:B] \sim \begin{bmatrix} 1 & 1 & 0 & | & 7 \ 0 & 1 & 0 & | & 4 \ 0 & 0 & 1 & | & -2 \end{bmatrix}

R1 - R2

[A:B] \sim \begin{bmatrix} 1 & 0 & 0 & | & 3 \ 0 & 1 & 0 & | & 4 \ 0 & 0 & 1 & | & -2 \end{bmatrix}

Now the matrix is transformed to reduced row echelon form, by using back substitution,

we can write the solution of the system as:

x = 3 ; y = 4; z = -2

Problems

Solve the following system of equations using the Gauss Jordan Elimination method.

Q.2 4y + z = 2
2x + 6y - 2z = 3
4x + 8y - 5z = 4

Q.3 x + 2y - 3z = 2
6x + 3y - 9z = 6
$$7x + 14y - 21