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. 51作业君版权所有
