程序代写代做代考 AI C Back to the motivating problem:

Back to the motivating problem:
Fall 2020
Prof.Jiang@ECE NYU 63
Lecture II
Solving m equations for n unknowns:
a x a x b 111 1nn1
 
a x a x b 211 2nn2
Ax  b. a x a x b
 m11 mnnm

When does a solution exist? When unique?
Both n and m are large

Extensions:
• Case 2: More unknowns
Three Cases
• Case 1: The same number of unknowns as the number of equations.
• Case 3: Less unknowns
Fall 2020 Prof.Jiang@ECE NYU 64

A Basic Result for Case 1
If the square matrix A is nonsingular, i.e. det A  0, then the linear equation Ax  b has the unique solution
x  A1b.
Recall that the inverse A1 of a nonsingular
matrix A is defined as
A1AAA1 I.
Fall 2020 Prof.Jiang@ECE NYU
65

About the Matrix Inverse
• If a (square) matrix A is nonsingular, then its inverse is unique. That is,
AB  I  B  A1 BA  I  B  A1.
Fall 2020 Prof.Jiang@ECE NYU 66

•
The inverse of a nonsingular matrix A is defined as
Computation of the Matrix Inverse
1 T A1 detA cofA ,
where cof A is the cofactor matrix of A: ij 
cofA1 detA  , ij nn
A thematrixofordern1,afterdeleting ij
row i and column j from A.
Fall 2020 Prof.Jiang@ECE NYU 67

Proof of
1 T AdetA cofA
1
Use the row and column expansions of det A.

Fall 2020 Prof.Jiang@ECE NYU 68

Fall 2020
Prof.Jiang@ECE NYU 69
An Example
Solve the linear equation, using the above basic result:
12×1 
 1 4 4x2 5

Another Computational Method: Cramer’s Rule
For any n  n nonsingular matrix A  aij ,
the linear equation Ax  b has the unique solution:
xjj ,j1,2,,n det A
where  j is the determinant of the matrix formed by replacing the j-th column of A by b. For example,
baa 1 12 1n
1det  ,etc b a  a 
Fall 2020
 n n2 nn 
Prof.Jiang@ECE NYU 70

Fall 2020
Prof.Jiang@ECE NYU 71
Proof of Cramer’s Rule
Consider the solution 1 T
xA b[cofA] b/detA.
1 So,xjdetA
 i1
i j
1 (detA)b
1 detA j
n
because, by the j-column expansion of  j ,
n
i j
j 1(detA)b.
i1
ij i
ij i

An Example
Solve the linear equation, using Cramer’s Rule: 12×1
  1
4 4x2 5
Fall 2020 Prof.Jiang@ECE NYU 72

Question
When is matrix A invertible?
Fall 2020 Prof.Jiang@ECE NYU 73

A Necessary and Sufficient Condition
The linear equation Ax  b is solvable for every b, ifandonlyif detA0.
Fall 2020 Prof.Jiang@ECE NYU 74

Proof
The sufficiency is proved above.
For the necessity, take the basis vectors:
 
100
010 e1  , e2  , , en  .
      
001

Then, for each 1 i  n, Ax  ei has solution xi.
So, AX I, withX [x1,,xn],
implying det A  0, because det( A) det( X )  1. Fall 2020 Prof.Jiang@ECE NYU 75

Comments
 In the proof, the following important fact was
used:
det( AB)  det Adet B
for any nn matrices A and B.
If detA  0, then
 for some vectors b, Ax  b has no solution;  for other vectors b, the equation may have
an infinite number of solutions!
Fall 2020 Prof.Jiang@ECE NYU 76

Homogenous Equations (b=0) Question:
When does a general homogenous equation Ax  0
have a nonzero solution x  0?
In other words, when are the column vectors of A
linearly dependent?
Fall 2020 Prof.Jiang@ECE NYU 77

•
Linear combination of vectors:
•
Linear independency:
Fall 2020
Prof.Jiang@ECE NYU 78
Review of Terminologies
n
 x is a linear combination of vectors x , , x .
ii1n i1
n ixi 0  1 2 n 0. i1

Review of Terminologies
• Linear dependency: n
x 0   0foratleastonej.
iij i1
Fall 2020 Prof.Jiang@ECE NYU 79

Review of A Basic Result
The vectors x , x , , x are dependent 12n
if and only if one of the vectors is some linear combination of the other vectors. That is, j and constants i so that
Fall 2020
Prof.Jiang@ECE NYU
80
xj ixi. i j

Fall 2020
Prof.Jiang@ECE NYU 81
Examples Revisited
Are the following vectors linearly dependent or independent?
1) Consider the vectors
  x1,y3
2 4  
2) Consider the vectors
 x1,y3,z5
2 4 8 

Homogenous Equations
A general homogenous equation
Ax0, Ann
has a nonzero solution x  0.

det A  0.
Fall 2020 Prof.Jiang@ECE NYU 82

Fall 2020
that det A  0.
Prof.Jiang@ECE NYU 83
Sketch of Proof
Let a1, a2, , an be the columns of A. So, we can rewrite Ax as
Ax  x a1  x a2  x an 12n
Thus, Ax  0 has a nonzero solution iff the columns of A are dependent.
Using Fact 4 of determinants, it follows

Case 2: More Unknowns In this case, consider
Ax  0 fornonsquareAmn, withmn.
Fall 2020 Prof.Jiang@ECE NYU 84

A Fundamental Result
The linear homogeneous equation with more unknowns, Ax0, Amn, mn
always has a solution x  0n.
Fall 2020 Prof.Jiang@ECE NYU 85

Sketch of Proof (m < n) Lemma: If p linearly independent vectors xi  are linear combination of q vectors x i  q  i j y j , 1  i  p  j1 then, q  p. Fall 2020 Prof.Jiang@ECE NYU 86 i1 yj j1 , i.e., q p Fall 2020 n Prof.Jiang@ECE NYU 87 Sketch of Proof (mn)
 Necessity: If one n  n submatrix A of A is 1
nonsingular, we can rearrange A so that
A  nn
A 1 , withA ,A
(mn)n Then, Ax  0 implies A x  0 and thus x  0.
A1 2 2
1
Fall 2020 Prof.Jiang@ECE NYU 92

 Sufficiency: Assume now all n  n submatrices of A are singular. Let r  n be the largest number of rows of A that are linearly independent, i.e., rank(A). Let’s decompose A into
AB, withBrn, C(mr)n, C

and the r rows of B are linearly independent. Clearly, Bx  0 has a nonzero solution x  0, which is also solution to Cx  0, because each row
of C is linear combination of the rows of B.
Fall 2020 Prof.Jiang@ECE NYU 93
Case 2

Corollary
The dimension of the null space of Amn isnrank(A):nr. Thatis,
dim xn : Ax0 nrank(A). 
Remark:
nT  N(A)R(A )
Fall 2020 Prof.Jiang@ECE NYU 94

Fall 2020
Prof.Jiang@ECE NYU 95
Toprovedim xn : Ax0 nr, 
let us decompose A  B, with the r rows of Brn C

linearly independent. Thus, Ax  0  Bx  0
 x
RearrangeB sothat B B 1 0, with detB 0.
12x 1 2
withB rr, B r(nr), x r, x nr. 1212
Then, B x  B x  0, or equivalently, 11 22

B1B 
x 1 2 x2, whichcompletestheproof.
x  B1B x , x free parameters 11222
 I(nr)(nr)  

Inhomogeneous Equations
GivenAa  andbb
, solvexfor
ij mn
a x a x b
i
111 1nn1 a x a x b
m1 
211 2nn2 
 
Axb. a x a x b
m11 mnnm
Fall 2020 Prof.Jiang@ECE NYU
96

A Fundamental Result
Consider Ax  b.
 It has a solution xn if and only if
rankArankB, forBA bm(n1).
 When rankA  rankB, all the solutions x take the form:
xxp xh
wherexp anyparticularsolutionofAxb;
xh  solutions to the homogeneous eq. Ax  0. Fall 2020 Prof.Jiang@ECE NYU 97

Proof of the Main Theorem
1) As seen previously, Ax  b can be rewritten as: xa1xa2xan b.
12n
When rank(A)  rank(B), b is linear combination
n
of the columns a i1 of A, so the above eq. has
 i a solution.
The converse is also true.
Fall 2020 Prof.Jiang@ECE NYU 98

Proof of the Main Theorem
2) For any general solution x of Ax  b and for any special solution xp of Ax  b, it is easily seen that
Axxp 0.
So,xxp N(A), i.e.,xxp xh, orequivalently
xxp xh.
Fall 2020 Prof.Jiang@ECE NYU 99

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 xp , then it may have an infinite number of solutions.
Fall 2020 Prof.Jiang@ECE NYU 100

Fall 2020
has no solution x2.
Prof.Jiang@ECE NYU 101
2x 4x 0 12
3x 6x 0 12
Example 1
The following inhomogeneous equation x 2x 1
12

Fall 2020
Prof.Jiang@ECE NYU 102
12
2x 4x 10 12
3x 6x 15 12
Example 2
The following inhomogeneous equation x 2x 5
has an infinite number of solutions
xxp xh
52  , .

0 1 

Application to an Optimization Problem
Fall 2020
Prof.Jiang@ECE NYU 103
Given m (noisy) observations b ,,b , and 1m
(experimental)variablesai (ai1,,ain), find the best possible values x , x , , x
to match
bxxaxa , 1im.
i01i1 nin Or, equivalently, to minimize
m
Pbx xa xa 2.
i01i1 nin i1
01n

Fall 2020
Prof.Jiang@ECE NYU 104
Necessary Condition
Asolutionxx x xtothe(nonlinear) 01n
optimization problem is often called “least-squares solution”.
It must satisfy the 1st-order necessary conditions:
P xj
0, j0,1,,n
 abxxaxa0,
m
iji01i1 nin
i1
with ai0 1.

Fall 2020
Prof.Jiang@ECE NYU
m 105
Normal Equation
The necessary conditions can be written in compact matrix form:
TT
A Ax  A b normal equation
where
1 a  a 
b   1 
 11 1n 
A     
m(n1) 
1a a  m1 mn
, b  . b

Comment
It is interesting to note that finding an (optimal) least-squares solution x boils down to
solving the inhomogeneous normal equation!
Fall 2020 Prof.Jiang@ECE NYU 106

Sufficiency
A solution x to the normal equation AT Ax  AT b does minimize the sum of squares, P.
Indeed, for any other vector y : x  z, Ayb2  (Axb)Az2
 Axb 2 2(Az)T (Axb) Az 2
 Axb 2  Az 2
 Axb2.
Fall 2020 Prof.Jiang@ECE NYU 107

Further Comments
T  T (n1)(n1) 1) If det A A  0, i.e., A A
is nonsingular, then the least-squares solution x to the best linear fit problem is unique.
2) If detAT A 0, many possible best fits; because AT Az  0 has infinitely many nontrivial solutions z  0,
thus,zT AT Az Az 2 0, formanyz0.
Fall 2020 Prof.Jiang@ECE NYU 108

Fall 2020
Prof.Jiang@ECE NYU 109
An Example
Findthebestlinearfitbxcol(1)a1x a2x 012
for the data 110
 
201 b ,a1,a2 .
0  1 1  
1 2 1 

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:
b  17col(1,…,1)  13a1  2a2. 663
Fall 2020 Prof.Jiang@ECE NYU 110

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”.
Fall 2020 Prof.Jiang@ECE NYU 111

1. Consider the matrix 1 4 7
A2 5 8. 
3 6 9 
Homework #2
What is the null space of A? What is the rank of A? What is the dimension of the null space?
Fall 2020 Prof.Jiang@ECE NYU 112

Homework #2
2. For any pair of nn matrices A, B,
show that det(AB)  det(BA)  det Adet B.
3. Give some simple examples to show that AB  BA.
Fall 2020 Prof.Jiang@ECE NYU 113

Homework #2
4. Consider linear equations of the form
x 2x 3x 4x 0, 1234
2x 4x  x  x 0. 121324
What is the range of parameters 1,2  for which the equations have nonzero solutions?
Also, find all nonzero solutions.
Fall 2020 Prof.Jiang@ECE NYU 114