2026 Prof.Jiang@ECE NYU 65
Lecture II
Linear Equation Theory
Back to the motivating problem:
11 1 1 1
21 1 2 2
1 1
Solving equations for unknowns:
.

When does a solution exist? When unique?

n n
n n
m mn n m
m n
a x a x b
a x a x b
Ax b
a x a x b
          




Both n and m are large
2026 Prof.Jiang@ECE NYU 66
Three Cases
• Case 1: The same number of unknowns
as the number of equations (n = m)
• Case 2: More unknowns (n > m)
• Case 3: Less unknowns (n < m)
Extensions:
A is a fat matrix
A is a tall matrix
A is a square matrix
2026 Prof.Jiang@ECE NYU 67
A Basic Result for Case 1
1
1
If the square matrix is , i.e.
det 0, then the linear equation
has the unique solution
.
Recall that the inverse of a nonsingular
matrix
nonsingul
is defined as

r

aA
A Ax b
x A b
A
A


 

1 1 .A A AA I  
2026 Prof.Jiang@ECE NYU 68
About the Matrix Inverse
• If a (square) matrix A is nonsingular, then its
inverse is unique. That is,
1
1.
AB I B A
BA I B A


  
  
2026 Prof.Jiang@ECE NYU 69
Computation of the Matrix Inverse
• The inverse of a nonsingular matrix A is defined
as
   
 
11 det cof ,
where is the cofactor matrix of :
cof 1 det ,
the matrix of order 1, after deleting
row and column fro
cof
m .
T
i j
ij
n n
ij
A A A
A
A A
A n
i j A
A




  
 

2026 Prof.Jiang@ECE NYU 70
Proof of    11 det cof TA A A 
Use the row and column expansions of det .A
2026 Prof.Jiang@ECE NYU 71
An Example
Solve the linear equation, using the above basic
result:
1
2
1 2 1
4 4 5
x
x
             
2026 Prof.Jiang@ECE NYU 72
Another Computational Method:
Cramer’s Rule
 For any matrix ,
the linear equation has the solution:
, 1, 2, ,
det
where is th
uniq
e de
nonsingu
terminant of the matrix formed by
replacin
ue
g the -
lar
th column
ij
j
j
j
n n A a
Ax b
x j n
A
j
 

 


1 12 1
1
2
of by . For example,

det , etc

n
n n nn
A b
b a a
b a a
       

   

2026 Prof.Jiang@ECE NYU 73
Proof of Cramer’s Rule
   
 
 
1
1
1
1
1
Consider the solution
[cof ] / det .
, det 1 (det )
det
because, by the column expansion- of ,
1 (det ) .
T
n
i j
j ij i
i
j
j
n
i j
j ij i
i
x A b A b A
So x A A b
A
j
A b

 




 
 
 

  


2026 Prof.Jiang@ECE NYU 74
An Example
Solve the linear equation, using Cramer’s Rule:
1
2
1 2 1
4 4 5
x
x
             
Question
2026 Prof.Jiang@ECE NYU 75
When is matrix A invertible?
2026 Prof.Jiang@ECE NYU 76
A Necessary and Sufficient
Condition
The linear equation is solvable for ,
if and only if det 0.
everyAx b b
A


2026 Prof.Jiang@ECE NYU 77
Proof
1 2
The sufficiency is proved above.
For the necessity, take the basis vectors:
1 0 0
0 1 0
, , , .
0 0 1
Then, for each 1 , has solution .
, , wi
n
i i
e e e
i n Ax e x
So AX I
                                
  

  
1th [ , , ],
implying det 0, because det( ) det( ) 1.
nX x x
A A X 
 
2026 Prof.Jiang@ECE NYU 78
Comments
 In the proof, the following important fact was
used:
det( ) det det
for any matrices and .
AB A B
n n A B



If det 0,
for some vectors , has no solution;
for other vectors ,
!
A then
b Ax b
b the equation may have
an infinite number of solutions

 

2026 Prof.Jiang@ECE NYU 79
Homogenous Equations (b=0)
Question:
When does a general homogenous equation
0
have a solution 0?nonzero
Ax
x


In other words, when are the column vectors of A
linearly dependent?
2026 Prof.Jiang@ECE NYU 80
Review of Terminologies
• Linear combination of vectors:
• Linear independency:
1
1
is a linear combination of vectors , , .
n
i i n
i
x x x

 
1 2
1
0 0.
n
i i n
i
x

          
2026 Prof.Jiang@ECE NYU 81
Review of Terminologies
• Linear dependency:
1
0 0 for at least one .
n
i i j
i
x j

    
2026 Prof.Jiang@ECE NYU 82
Review of A Basic Result
1 2The vectors , , , are dependent
one of the vectors is some
linear combination of the other vectors.
That is, and constants so that
if and

onl

y if
.
n
i
j i i
i j
x x x
j
x x

 
 

2026 Prof.Jiang@ECE NYU 83
Examples Revisited
Are the following vectors linearly dependent or
independent?
1) Consider the vectors
1 3
,
2 4
2) Consider the vectors
1 3 5
, ,
2 4 8
x y
x y z
          
                 
2026 Prof.Jiang@ECE NYU 84
Homogenous Equations
A general hom ogenous equation
0 ,
has a nonzero solution 0.
det 0.
n nAx A
x
A
 




2026 Prof.Jiang@ECE NYU 85
Sketch of Proof
1 2
1 2
1 2
Let , , , be the columns of .
So, we can rewrite as

, 0 has a nonzero solution iff
the columns of are dependent.
Using Fact 4 of determinants, it follows
that de
n
n
n
a a a A
Ax
Ax x a x a x a
Thus Ax
A
   



t 0.A 
2026 Prof.Jiang@ECE NYU 86
Case 2: More Unknowns
In this case, consider
0
for , with .m nnonsquare
Ax
A m n

 
A is a fat matrix
2026 Prof.Jiang@ECE NYU 87
A Fundamental Result
The linear homogeneous equation with more unknowns,
0, ,
always has a solution 0 .
m n
n
Ax A m n
x
  
 


2026 Prof.Jiang@ECE NYU 88
Sketch of Proof (m < n)
 
 
1
1
1
: If linearly independent vectors
are linear combination of vectors , i.e.,
, 1
,
Lemma
.
p
i i
q
j j
q
i ij j
j
p x
q y
x y i p
then q p



   


2026 Prof.Jiang@ECE NYU 89
Sketch of Proof (m 
1
1
1
1
, the columns
of in ( ) must be
linearly dependent.
, 0 0
0

By means of this l

emm
.
0
a
ni m
i
n
n
n
a A m n
Thus Ax x a x a
x
x
x
 
    
                 


 
End of Proof
2026 Prof.Jiang@ECE NYU 90
Numerical Example
Find all nonzero solutions for
1 2 3
1 2 3
2 3 0,
9 28 0.
x x x
x x x
  
  
2026 Prof.Jiang@ECE NYU 91
Comment
The set of solutions to Ax=0 is called null
space of and often denoted as null(A):
It is easy to show that null(A) is a linear
vector space with dimension less than or
equal to n.
,m nA 
 ( ) : 0nnull A x Ax  
Question: What is the dimension of this null space?
2026 Prof.Jiang@ECE NYU 92
Case 3: Fewer Unknowns
In this case, consider
0
for nonsquare , with .m n
Ax
A m n

 
A is a tall matrix
2026 Prof.Jiang@ECE NYU 93
A Fundamental Result
The homogeneous equation with unknowns,
0, ,
has a solution 0
every determinant formed from rows of
be zero. In other words,
fewe
rank( ) .
r
m n
n
Ax A
x
n n n
A A
m n
n
  
 





2026 Prof.Jiang@ECE NYU 94
Sketch of Proof (m>n)
1
1
1 2
2
1
( )
: If one submatrix of is
nonsingular, we can rearrange so that
, with ,
Then, 0 implies 0 an
Nece
d thus 0
s it
.
s y
n n m n n
n n A A
A
A
A A A
A
Ax A x x
  
 
     
  
 
2026 Prof.Jiang@ECE NYU 95
: Assume now all submatrices
of are singular. Let be the largest number
of rows of that are linearly independent, i.e.,
( ). Let's decompose into

r
,
Sufficienc
wit
ank
y
h , r n
n n
A r n
A
A A
B
A B
C

 

    
 ( ) ,
and the rows of are linearly independent.
Clearly, 0 has a nonzero solution 0,
is also solution to 0, because each row
of is linear combination of the rows of .
m r nC
r B
Bx x
which Cx
C B
 
 


Case 2
2026 Prof.Jiang@ECE NYU 96
Corollary:
Rank nullity theorem
 
The dimension of the null space of
is : . That is,
dim : 0 ( ).
( )
m n
n
rank
A
n n
x A
A r
x n rank A

  
   


( ) ( )n TN A R A Remark:
2026 Prof.Jiang@ECE NYU 97
 
  11 2 1
2
( )
1 2
linearly independent
To prove dim : 0 ,
let us decompose , with the rows of
. Thus, 0 0
Rearrange so that 0, with det 0.
with , ,
n
r n
r r r n r
x Ax n r
B
A r B
C
Ax Bx
x
B B B B
x
B B x

  
   
    
  
     
 


  1 2
1 1 2 2
1
1 1 2 2 2
1
1 2
2
( ) ( )
free pa
, .
Then, 0, or equivalently,
,
, which completes the proof.

rameters

r n r
n r n r
x
B x B x
x B B x x
B B
x x
I



  
 
 
 
      
 
2026 Prof.Jiang@ECE NYU 98
Inhomogeneous Equations
    1
11 1 1 1
21 1 2 2
1 1
Given and , solve for
.

ij i mm n
n n
n n
m mn n m
A a b b x
a x a x b
a x a x b
Ax b
a x a x b
 
          




2026 Prof.Jiang@ECE NYU 99
A Fundamental Result
  ( 1)
Consider .
It has a solution if and only if
rank rank , for .
When rank rank , all the solutions
take the form:

partic

where any ar ul
n
m n
p h
p
Ax b
x
A B B A b
A B x
x x x
x
 

 
 
 



 

solution of ;
solutions homogento the eq. 0.eoush
Ax b
x Ax

 
2026 Prof.Jiang@ECE NYU 100
Proof of the Main Theorem
 
1 2
1 2
1
1) As seen previously, can be rewritten as:
.
When ( ) ( ), is linear combination
of the columns of , so the above eq. has
a solution.
The converse is also tru
n
n
ni
i
Ax b
x a x a x a b
rank A rank B b
a A

   


e.
2026 Prof.Jiang@ECE NYU 101
Proof of the Main Theorem
 
2) For any general solution of and for any special
solution of , it is easily seen that
0.
So, ( ), i.e., , or equivalently

p
p
p p h
p
x Ax b
x Ax b
A x x
x x N A x x x
x x


 
   
 .hx
2026 Prof.Jiang@ECE NYU 102
Comments
• Unlike the homogeneous case, an
inhomogeneous equation may have no solution
(trivial or nontrivial), because of the rank
condition.
• When it has one solution , then it may have
an infinite number of solutions.
px
2026 Prof.Jiang@ECE NYU 103
Example 1
1 2
1 2
1 2
2
The following inhomogeneous equation
2 1
2 4 0
3 6 0
has no solution .
x x
x x
x x
x
 
 
 

2026 Prof.Jiang@ECE NYU 104
Example 2
1 2
1 2
1 2
The following inhomogeneous equation
2 5
2 4 10
3 6 15
has an infinite number of solutions

5 2
, .
0 1
p h
x x
x x
x x
x x x
 
 
 
 
             
2026 Prof.Jiang@ECE NYU 105
Application to an Optimization Problem
1
1
0 1
0 1 1
Given (noisy) observations , , , and
(experimental) variables ( , , ),
find the best possible values , , ,
to match
, 1 .
Or, equivalently, to

minimize
m
i i in
n
i i n in
m b b
a a a
x x x
b x x a x a i m
P b

     





 20 1 1
1
.
m
i i n in
i
x x a x a

    
2026 Prof.Jiang@ECE NYU 106
Necessary Condition
 0 1
0
least-squares solution
A solution to the (nonlinear)
optimization problem is often called
" ".
It must satisfy the 1st-order necessary conditions:
0 , 0,1, ,

n
ij i
j
x x x x
P j n
x
a b x x

  
  


 1 1
1
0
0,
1.
m
i n in
i
i
a x a
with a

  

 
2026 Prof.Jiang@ECE NYU 107
Normal Equation
111 1
( 1)
1
normal equation
The necessary conditions can be written in
compact matrix form:

where
1
, .
1
T T
n
m n
m mn m
A Ax A b
ba a
A b
a a b
 

                

     

2026 Prof.Jiang@ECE NYU 108
Comment
It is interesting to note that finding an (optimal)
least-squares solution x boils down to
solving the inhomogeneous normal equation!
2026 Prof.Jiang@ECE NYU 109
Sufficiency
2 2
2 2
2 2
2
A solution to the normal equation
minimize the sum of squares, .
Indeed, for any other vector : ,
( )
2( ) ( )
.
T T
T
x A Ax A b
does P
y x z
Ay b Ax b Az
Ax b Az Ax b Az
Ax b Az
Ax b

 
   
    
  
 
2026 Prof.Jiang@ECE NYU 110
Further Comments
 
 
( 1) ( 1)1) If det 0, . .,
is nonsingular, then the least-squares solution
to the best linear fit problem is .
2) If det 0, many possible best fits; because
0 has infi
un
n
que
it
i
T T n n
T
T
A A i e A A
x
A A
A Az
   



2
ely many nontrivial solutions 0,
, 0, for many 0.T T
z
thus z A Az Az z

  
2026 Prof.Jiang@ECE NYU 111
An Example
1 2
0 1 2
1 2
Find the best linear fit (1)
for the data
1 1 0
2 0 1
, , .
0 1 1
1 2 1
b x col a x a x
b a a
  
                                 
2026 Prof.Jiang@ECE NYU 112
Solution
First, note that there is no (exact) solution to the
linear equation Ax=b.
However, there is a unique (least-squares) best
linear fit:
1 217 13 2 col(1,...,1) .
6 6 3
b a a  
2026 Prof.Jiang@ECE NYU 113
Remark
If you want to know more about optimization,
it is a good idea to take the sequence
class ECE-GY 6233 “Systems
Optimization Methods”.
2026 Prof.Jiang@ECE NYU 114
Homework #2
1. Consider the matrix
1 4 7
2 5 8 .
3 6 9
What is the null space of ? What is the rank of ?
What is the dimension of the null space?
A
A A
      
2026 Prof.Jiang@ECE NYU 115
Homework #2
2. For any pair of matrices , ,
show that det( ) det( ) det det .
3. Give some simple examples to show that
.
n n A B
AB BA A B
AB BA

 

2026 Prof.Jiang@ECE NYU 116
Homework #2
 
1 2 3 4
1 2 1 3 2 4
1 2
4. Consider linear equations of the form
2 3 4 0,
2 4 0.
What is the range of parameters , for which
the equations have nonzero solutions?
Also, find all nonzero
x x x x
x x x x
   
     
 
solutions.

学霸联盟