National Chiao-Tung University

Institute of Electronics

Solving Linear Equations (I)

Institute of Electronics, NYCU, Taiwan

桑梓賢 Tzu-Hsien Sang

Thanks to Prof. Carrson Fung for some

of the materials in the lecture PPTs.
1
• Vectors and linear equations
• The idea of elimination
• Elimination using matrices
• Matrix operations
• Inverse matrices
• Factorization A = LU
• Transposes and permutations

2
Vectors and linear equations

• Recall the example of linear example; if instead the result is

unknown and the combination coefficients are unknown.
1 0 0 𝑐𝑐 𝑐𝑐
−1 1 0 𝑑𝑑 = 𝑑𝑑 − 𝑐𝑐
0 −1 1 𝑒𝑒 𝑒𝑒 − 𝑑𝑑

1 0 0 𝑥𝑥1 𝑏𝑏1
−1 1 0 𝑥𝑥2 = 𝑏𝑏2
0 −1 1 𝑥𝑥3 𝑏𝑏3

𝐴𝐴𝒙𝒙 = 𝒃𝒃
where 𝐴𝐴 and 𝒃𝒃 are given and 𝒙𝒙 is unkown.

• Now we have a set of linear equations.

3
• Row-centric view

x − 2y = 1
3 x + 2 y = 11

4
• Column-centric view
=x − 2y 1 1   −2  1 
⇒ x + y  = 11 =
b =+
xu yv
3x + 2 y =
11  
3    
2

5
Matrix form

=x − 2y 1 1 −2   x  1 
⇒ Ax = 3 2   y  = 11 = b
3x + 2 y =
11     

General system matrix form

a11 x1 + a12 x2 +  + a1n xn =
b1
 , Ax = b
am1 x1 + am 2 x2 +  + amn xn =
bm
where
 a11  a1n   A(1,1)  A(1, n) 
=A =      
   ,

 am1  amn   A(m,1)  A(m, n) 
aij : entry (or component) in row i and column j
 x1   b1 
=x =   : the unknown vector, b 
 
 xn  bm 

6
  aTr1   aTr1x 
   
=
Traditional (row) method: Ax =  x   
aTrm  aTrm x 
   
Ax is a dot product between the rows of A and the column vector x

 x1 
column method: Ax= [a c1  a cn ]   = x1a c1 +  + xna cn
 xn 
b is a linear combination of the vectors ac1, …, acn

7
Examples of three variables

8
The idea of elimination (I)

• Eliminations
– The world’s first systematic way of solving systems of linear
equations: 九章算術(東漢) 卷第八 方程
– Use 籌算 (rod calculus) to represent linear equations (the
equation reads vertically)

– Use 直除遍乘法 to do basically the same thing as what the

Gauss elimination does.

9
The idea of elimination (II)

• Goals
– Gauss Elimination (GE): To triangularize A such that the
solution can be found by back substitution
– Gauss-Jordan elimination (GJ): To diagonalize A (as much as
possible) such that solution can be found by inspection
• Easy way to compute inverses
– Reveal location of pivots
• Identify free and basic/pivot variables
– Identification of C(A), N(A), C(AT), N(AT)
Column space and null space,
we will talk about them later.

• Do the same operations to both sides of the equation.

10
Example of elimination

• Note that we are not after any fancy way to get solutions fast
by hands. We are looking for an algorithm that can be easily
programmed and executed on COMPUTERS.
• These examples and exercises are to make you familiar and
comfortable with the concept and the algorithm.

11
No solution and infinitely many solutions

12
GE and GJ

• The matrix A is not square to show the general case.

 0 0 −2 0 7 12  (Every steps performed here
=A  2 4 −10 6 12 28 have to be applied to b as well.
Can be done in one shot by
 2 4 −5 6 −5 −1
performing GE and GJ on the
augmented matrix [A | b])
2 4 -10 6 12 28
Interchange rows:  2 4 -5 6 -5 -1 
 0 0 -2 0 7 12 
2 4 -10 6 12 28 
-1 row 1 + row 2:  0 0 5 0 -17 -29 
 0 0 -2 0 7 12 
  Blue letters show the
 2 4 -10 6 12 28  positions of pivots.
2  
row 2 + row 3:  0 0 5 0 -17 -29  = U
5  1 2 
 0 0 0 0 
 5 5 
Row-echelon form
13
GJ

 
 2 4 0 6 0 14 
   
2 4 -10 6 12 28 2 row 2 + row 1:  0 0 5 0 0 5 
   1 2
85 row 3 + row 2:  0 0 5 0 0 5 0 0 0 0 
  5 5
1 2
0 0 0 0 
 5 5
1
  to row 1
2 2
4 -10 6 0 4
  1 2 0 3 0 7 
-60 row 3 + row 1:  0 0 5 0 0 5 1
to row 2: 0 0 1 0 0 1  = R
 1 2 5  
0 0 0 0  0 0 0 0 1 2 
 5 5
5 to row 3 Reduced row-echelon form

14
Elimination using matrices

 0 0 −2 0 7 12  Remember that very steps performed

=A  2 4 −10 6 12 28 to A have to be applied to b as well.
 2 4 −5 6 −5 −1

0 1 0  1 0 0 
=
Row permutation: P1 =1 0 0  , P2 0 0 1 
 
0 0 1  0 1 0 
 
 1 0 0   1 0 0 
 −1 1 0  , E =  
Gaussian elimination: E21 =
  32  0 1 0 
 0 0 1   2 
0 1
 5 
1 
2 0 0
1 0 0  1 0 −60  1 2 0   
=
Gauss-Jordan 
Elim.: E23 =  
0 1 85 , E13 0 1=  
0  , E12 = 
0 1 0 , D  0
1
0 
 5 
0 0 1  0 0 1  0 0 1  
0 0 5 
 

=
E32 E21P2 P1A U=
; DE12 E13E23 U R

15
Augmented matrices

• Operations on both sides can be performed in one shot by

using matrix multiplication by concatenating A and b into an
augmented matrix
 a11 a12  a1n b1 
a a22  a2 n b2 
[ A b ] =  21  
 
 am1 am 2  amn bm 
Example:
=
 2x + 4 y − 2z 2  2 4 −2 2 
  
 4 x + 9 y − 3 z = 8 ⇒ [ A b ] =  4 9 −3 8 
−=  −2 −3 7 10 
 2 x − 3 y + 7 z 10
 1 0 0
Let E21 =  −2 1 0 
 0 0 1 
 1 0 0   2 4 −2 2   2 4 −2 2 
 −2 1 0   4 9 −3 8  =
⇒ E21 [ A b ] =  
    0 1 1 4
 0 0 1   −2 −3 7 10   −2 −3 7 10 

16
Consistent vs. inconsistent

System of Linear Equations

Inconsistent Consistent

More than one

No solution Unique solution
solution

17
Elementary matrices

• An n×n matrix is called elementary (or elimination) matrix if it

can be obtained from the identity matrix In by performing a
single elementary row operation
• n×n identity matrix: 1 0 0 
I n = 0  0 
– InA = AIn = A 0 0 1 

• Three types of row operations

2 0 0 1 0 0  1 0 3 
Scaling:  0 1 0  , Permutation: 0 0 1  , Replacement: 0 1 0 
 0 0 1  0 1 0  0 0 1 

18
Row- and Reduced Row-Echelon Form

1. If a row does not consist entirely of zeros, then the first

nonzero number in the row is a 1. (leading 1)
2. If there are any rows that consist entirely of zeros, then they
are grouped together at the bottom of the matrix
3. In any two successive rows that do not consist entirely of
zeros, the leading 1 in the lower row occurs farther to the
right than the leading 1 in the higher row
4. Each column that contains a leading 1 has zeros everywhere
else
• Row-echelon form satisfies properties 1-3
• Reduced row-echelon form satisfies properties 1-4
Examples
0 1 −2 0 1
1 4 3 7  0 0 0 1 3 1 0 0 4 
0 1 6 2  0 0 1 0 7 
0 0 1 5  0 0 0 0  
  0 0 1 −1
  0 0 0 0 0

19
Summary: GE and GJ

• Step 1:
Locate the leftmost column that does not consist entirely of zeros
• Step 2:
Interchange the top row with another row, if necessary, to bring a nonzero entry to
the top of the column found in Step 1
• Step 3:
If the entry that is at the top of the column found in Step 2 is a, multiply the first
row by 1/a in order to introduce a leading 1
• Step 4:
Add suitable multiples of the top row to the rows below so that all entries below the
leading 1 become zeros
• Step 5:
Now cover the top row in the matrix and begin again with Step 1 applied to the
submatrix that remains. Continue in this way until the entire matrix is in row-
echelon form
• Step 6 (Gauss-Jordan only step):
Beginning with the last nonzero row and working upward, add suitable multiples of
each row to the rows above to introduce zeros above the leading 1’s

20
Matrix operations

• Column matrix (column vector)

– One column matrix, e.g. 3×1
• Row matrix (row vector)
– One row matrix, e.g. 1×4
• Scalar
– 1×1 matrix
• Main diagonal of A
– a11, a22, …, ann, can be denoted as {aii}, for i = 1,..,n
• Two matrices are equal if they have the same size and their corresponding
entries are equal
• Sum
– A+B = [aij + bij]
• Difference
– A-B = [aij - bij]
• Scalar multiplication
– cA = [caij]

21
• Linear combination of A1, A2, …, An with coefficients c1, c2, …, cn
– c1A1 + c2A2 + … + cnAn

• m×n all zero matrix

– 0m×n – all entries are zero

• Law for matrix operations

– Commutative law for addition
• A+B = B+A
– Distributive law for scalar multiplication
• c(A+B) = cA+cB
– Associative law for addition
• A+(B+C) = (A+B)+C
– Associative law for multiplication
• A(BC) = (AB)C
– Left distribution law
• A(B+C) = AB+AC
– Right distribution law
• (B+C)A = BA+CA

22
• Matrix multiplication: C = AB.
• The size of A is nxk and the size of B is kxm, then the size of
C is nxm. The element of C at the i-th row and j-th column
equals to the inner product between the i-th row of A and j-th
column of B.

23
• Power of a matrix: If A is a square matrix, then
– A0=In
– An=AA···A (n times)
– ArAs=Ar+s; (Ar)s=Ars
• Transpose
– AT is an n×m matrix if A is an m×n matrix, and (AT)ij = (A)ji
(interchange rows and columns)
• Properties of transpose
– (AT)T = A
– (A+B)T = AT+BT
– (AB)T = BTAT
– (Ax)Ty equals xTATy equals xT(ATy)

24
Symmetric matrices

• Symmetric matrix
– A square matrix is symmetric if A = AT (i.e. symmetric w.r.t. its main
diagonal)
– If A is an m×n matrix, then AT is an n×m matrix

• Hermitian symmetric matrix (or Hermitian matrix)

– A square matrix is symmetric if A = AH = A*T

• If A and B are symmetric matrices with the same size, and if k is any
scalar, then
– AT is symmetric
– A+B and A-B are symmetric
– kA is symmetric

• AAT and ATA are both square and symmetric

• Above applies equally to Hermitian matrices

25
Triangular matrices

• Lower (upper) triangular matrix

– A square matrix in which all of the entries above (below) the main
diagonal are zero
Lower Triangular Upper Triangular
 a11 0 0 0  a11 a12 a13 a14 
a 0  0 a a24 
 21 a22 0  22 a23
 a31 a32 a33 0 0 0 a33 a34 
   
 a41 a42 a43 a44  0 0 0 a44 

• Strict lower (upper) triangular matrix

– A square in which all of the entries above (below) the main diagonal
and the main diagonal are zero

26
• Properties of triangular matrices
– The transpose of a lower triangular matrix is upper triangular, and the
transpose of an upper triangular matrix is lower triangular
– The product of lower triangular matrices is lower triangular, and the
product of upper triangular matrices is upper triangular

• Therefore, from our example

U L−1A =
E32 E21 A =⇒ U

L−1

27
Diagonal matrices

• A square matrix in which all of the entries off the main

diagonal are zero

d1 0  0  d1k 0  0 
0  
 0  0 d2k  0 
Dk = 
d2
D=  
       
   k
0 0  dn   0 0  d n 

28