MATH1853 Maths I

Projection & Quadratic Form

Dr. Ngai WONG
Fall 2024
Parabola

Projection
Parabola

Projection
1
 Inner Product
• For two vectors u, v in n, the inner product is defined as
 v1 
v 
uT v= [u1 u2 ... un ]  2 = u1v1 + u2 v2 + ... + un vn
 
 
vn 
• It is obvious that uTv= vTu
• From inner product, we can define other attributes of a vector
• The length (or norm) of a vector v is defined as
v= vT v= v12 + v22 + ... + vn2

• It is easy to see that ||v||³0, and ||v||=0 iff v=0

• The distance between two vectors u, v in n is defined as
dist(u, v ) = u − v = (u1 − v1 ) 2 + (u2 − v2 ) 2 + ... + (un − vn ) 2

• Obviously, dist(u,v)=dist(v,u)
2
• Example: With u=[2 -5 -1]T and v=[3 2 -3]T, compute uTv and vTu
3
u v =[ 2 -5 -1]  2  =(2)(3) + (−5)(2) + (−1)(−3) =−1
T

 −3
2
vT u =[3 2 -3]  −5 = (3)(2) + (2)(−5) + (−3)(−1) =−1
 −1

• Example: Let v=[1 -2 2 0]T. Find a unit vector u in the same

direction as v.
– The norm of v is v= 12 + (−2) 2 + 22 + 0=
2
3
1  1/ 3 
   −2 / 3
1  −2 
– The unit norm vector is u = v / ||v||:
= u =  
3 2   2/3 
   
0  0 
– You can verify that ||u||=1
• Example: The distance between u=[7 1]T and v=[3 2]T is computed
as
|| u − v ||= (7 − 3) 2 + (1 − 2) 2 = 17

3
• For u, v, w in n, and c being a scalar, below are two properties of
inner product:
a. (u+v)Tw = uTw + vTw
b. (cu)Tv = c(uTv) = uT(cv)
• These two properties combined gives
(c1u1 + ... + c p u p=
)T w c1 (u1T w ) + ... + c p (uTp w )

• Remark: Another notation of uTv is u×v, which is called dot product

• Consider two vectors u, v in n, we compute

2
u + v =(u + v )T (u + v )
u+v v
=u u + 2u v + v v
T T T

2 2
= u + v + 2uT v u

• If uTv=0, we have ||u+v||2= ||u||2 + ||v||2. This is actually the Pythagoras'

theorem, when u and v are at 90 degree
• In this case, we say u, v in n are orthogonal u+v
v
to each other
u 4
• In general, the inner product uTv contains information about the
angle between u and v
• Consider the triangle on the right, using the law of cosines,
2 2 2
u − v = u + v − 2 u v cos ϑ

• Rearranging the equation gives

1 2
u + v − u−v 
2 2
ϑ
u v cos=
2 
1 2
u + v − u − v + 2uT v 
2 2 2
=
2 
= uT v
So we have the general result: u v = u v cos ϑ
T
•

• Of course, when J=90°, uTv=0, which is the definition for orthogonal

vectors
• Note that if u and v are not zero vectors, u and v being orthogonal
implies u and v are linearly independent (but the reverse is not
necessarily true)
5
 Orthogonal Sets
• A set of vectors {u1, u2,…, up} in n is said to be an orthogonal set
if uiTuj=0 for all i≠j
  3  −1  −1/ 2  
      −2  
• Example: Show that u=
1 1  , u =
2  2  , u=
3   is an orthogonal set
 1   1   7 / 2  
– We compute 

u1T u 2 = (3)(−1) + (1)(2) + (1)(1)= 0

u1T u3 = (3)(−1/ 2) + (1)(−2) + (1)(7 / 2) = 0
uT2 u3 =(−1)(−1/ 2) + (2)(−2) + (1)(7 / 2) =0

– Since each pair of distinct vectors are orthogonal, the set {u1,u2, u3} is
an orthogonal set
• If {u1, u2,…, up} in n is an orthogonal set, then they are linearly
independent, and hence is a basis for the subspace Span{u1, u2,…,
up }

6
• Let {u1, u2,…, up} in n be an orthogonal set, and be the basis of a
subspace W, then for each y in W, it can be expressed as
y= c1u1 + c2u 2 + ... + c p u p
The coefficients cj can be easily obtained as
yT u j
y u=
T
j (c1u1 + c2u 2 + ... + c p u p ) u j = c j u u j
T T
j ⇒ c=
j
uTj u j

• Example: The set {u1, u2, u3} in the last example is an orthogonal
basis for 3. Express y=[6 1 -8]T as a linear combination of the
basis. T T
y u1 T
y u2 y u3
– Based on the above result, y = u1 + u 2 + u3
u1 u1
T
u2 u2
T
u3 u3
T

– The inner products are computed as

y T u1 =
11, y T u 2 =
−12, y T u3 =
−33
u1T u1 11,
= = uT2 u 2 6,=
uT3 u3 33 / 2

– Putting these back into the linear combination expression:

y =u1 − 2u 2 − 2u3
7
 Orthogonal Projection
• Consider a vector y in n , we want to
decompose y into
y= yˆ + z
where ŷ is along the direction of u (in n)
and z is in the direction orthogonal to u
• For ŷ, we can write yˆ = α u for some unknown a
• By definition, z= y − yˆ is orthogonal to u, i.e.,
yT u
(y − α u)T u =
0= y T u − α uT u ⇒ α= T
u u
yT u
• Therefore, yˆ = T u
u u
• Notice that the expression of a is the same as the expansion
coefficient cj in the previous slide
• Therefore, the linear combination expression is to orthogonally
project y onto the (orthogonal) basis 8
• Example: Let y=[7 6]T and u=[4 2]T. Find the orthogonal projection
of y onto u. Also find the length of the component of y that is
orthogonal to u.
– The orthogonal projection is
yT u (7)(4) + (6)(2)  4  8 
=yˆ = u =
u u
T
(4)(4) + (2)(2)  2   4 
– The component orthogonal to u is
7  8   −1
y − yˆ =   −  =  
6   4   2 
– And the length of y − yˆ is
y − yˆ = (−1) 2 + 22 = 5
– Relationship between different vectors is shown below

9
 Orthonormal Sets
• An orthonormal set is a set of orthogonal vectors with the additional
property that each vector is of unit norm
• Example: Convert {v1, v2, v3} into an orthonormal set where
v1=[3 1 1]T, v2=[-1 2 1]T, v3=[-1 4 7]T,
– It can be easily shown that v1Tv2 = v1Tv3 = v2Tv3 = 0 Þ they are orthogonal
– However, their norms are not unity
– In particular,
= v1 11,
= v2 =6, v 3 66
3 / 11   −1/ 6   −1/ 66 
     
– Therefore, an orthonormal
= set is v 1 =1/ 11  , v
2 = 2/ 6 , v
3  4 / 66 
     
1/ 11   1/ 6   7 / 66 

• Let U be an m´n matrix with its columns being orthonormal vectors,

then uT  uT u uT u ... uT u 
1 1 1 1 2 1 n
 T  T 
u2  u
 2 = u u T
u ... u T
u
2 n
=UT U = [u1 u 2 ... u n ]  
1 2 2
In
    
   
uTn  u n u1 u n u 2 ... u n u n 
T T T

10
 • Let U be an m´n matrix with orthonormal columns and let x and y
be in n, then
a. || Ux || = || x ||
T T
(Try to prove them)
b. (Ux) (Uy) = x y
• Property a. says that the matrix U only changes the direction of x
but not its length
1/ 2 2 / 3 
   2
• Example:
= Let U =1/ 2 - 2 / 3 and x   . Verify U has orthonormal
 0 1/ 3   3 
 
columns. Then verify || Ux || = || x ||.
– First, the columns of U are orthonormal since
1/ 2 2 / 3 
1/ 2 1/ 2 0    1 0 
=UT U =  1/ 2 - 2 / 3   
 2 / 3 - 2 / 3 1/ 3  0 1/ 3  0 1
 
– Then, we compute
1/ 2 2/3 3
   2  
Ux = 1/ 2 - 2 / 3   =  −1 ⇒ Ux = 9 + 1 + 1 = 11 = x
 0 3
 1/ 3     1  11

• For a matrix with orthonormal columns, in case the matrix is further a
square matrix, we call it an orthonormal matrix*
• An orthonormal matrix is invertible, so
UT U =I ⇒ UT UU −1 =U −1 ⇒ UT =U −1
• The computation of the inverse of an orthonormal matrix is very easy, which
is just the transpose
• Furthermore,
UT =U −1 ⇒ UUT =UU −1 ⇒ UUT =I
• Interestingly, for an orthonormal matrix, not only the columns are
orthonormal, the rows are automatically orthonormal too!! (why?)
3 / 11 -1/ 6 1/ 66 
 
• Example: The matrix U = 1/ 11 2/ 6 - 4 / 66  is an orthonormal
 
1/ 11 1/ 6 7 / 66 
matrix because it is square and its columns are orthonormal. Verify it rows
are also orthonormal.
*Sometimes the term orthogonal matrix is used interchangeably with orthonormal matrix,
though the former is more general and covers also non-square matrices. 12
 Symmetric Matrices
• A symmetric matrix is a matrix such that AT=A
• Such matrix is necessarily square (why?)
• Its main diagonal elements are arbitrary
• Example: 0 -1 0   a b c 
1 0  
Symmetric: 0 -3 , -1 5 8  , b
 d e 
  0 8 -7 
 c e f 
1 -4 0 5 4 3 2
1 -3 
Nonsymmetric: 3 0  , -6 1 -4  , 4
 3 2 1 
  0 -6 1  3 2 1 0 

6 -2 -1
• Example: If possible, diagonalize the matrix A = -2 6 -1
-1 -1 5 

– The eigenvalues and eigenvectors of A can be shown to be real (treat it

as an exercise)
 −1  −1 1
λ1 =  1 ;
8 : v1 = λ 6
= : v  −1 ;
= λ 3
= : v 1
=
  2 2   3 3 
 0   2  1
13
 – It can be easily shown that {v1,v2,v3} are orthogonal
– But we know that orthonormal columns are even more useful when
computing inverse
– So, we introduce their normalized versions:
 −1/ 2   −1/ 6  1/ 3 
     
u1 =
 1/ 2  , u2 =
 −1/ 6  , u3 =
1/ 3 
 0     
   2 / 6  1/ 3 
– Then, we can write A=UDU-1 where (think about why normalization of
eigenvectors does not matter)
 −1/ 2 − 1/ 6 1/ 3  8 0 0 
   
U= 1/ 2 − 1/ 6 1/ 3  , D =
0 6 0 
  0 0 3 
 0 2/ 6 1/ 3 

– Since U is orthonormal, U-1=UT, and therefore A = UDUT

• The following result explains why the eigenvectors in the above
example are orthogonal
• If A is symmetric, then any two eigenvectors corresponding to
different eigenvalues are orthogonal

14
• Recall that if there is no symmetric information, eigenvectors
corresponding to different eigenvalues are linearly independent
• So the symmetric information leads to a stronger result
• The proof of the above result is simple:
– Suppose v1 and v2 are eigenvectors correspond to eigenvalues l1 and
l2, respectively, then
λ1 v1T v 2 (=
= λ1 v1 )T v 2 ( Av1 )T v 2
= v= because A is symmetric
1 A v2 v1T ( Av 2 )
T T

1 λ2 v 2
= v= λ2 v1T v 2
T

– Therefore, (λ1 − λ2 ) v1T v 2 =

0
– Since for distinct eigenvalues l1¹l2, we have v1Tv2=0
• The above result guarantees that if all the eigenvalues are distinct,
then a symmetric matrix can be diagonalized by an orthonormal
matrix
• But what if some eigenvalues have multiplicity greater than one?
• The following result gives us the answer
15
• For an n´n symmetric matrix A, the geometric multiplicity for each
eigenvalue l always equals the algebraic multiplicity of l

• This is a very good news since we can always represent the

eigenspace with a set of orthonormal basis vectors
 3 -2 4 
A = -2 6 2 
• Example: Diagonalize the matrix  
 4 2 3 

– It is found that the eigenvalues and eigenvectors are (prove it at home)

1   −1/ 2   −1 
λ1 = 0  , v =
7 : v1 =   λ3 =  −1/ 2 
−2 : v 3 =
  2  1 ;  
1   0   1 

– The dimension of eigenspace for l1=7 is 2, and v1 and v2 span the

eigenspace
– They are only linearly independent, but not orthogonal
– However, we can find two vectors that are orthogonal, and spanning the
same eigenspace

16
– By orthogonal projection, we can find the component of v2 that is
orthogonal to v1
Orthogonal projection
vT2 v1
z=2 v 2 − T v1 of v2 onto v1
v1 v1
 −1/ 2  1   −1/ 4 
= 1  − −1/ 2 0  =  1 
  2    
 0  1   1/ 4 
– {v1, z2} is an orthogonal set that spans the same eigenspace as {v1,v2}
– It can be easily shown that {v1, z2, v3} is an orthogonal set
– Now, we normalize {v1, z2, v3} to give an orthonormal set {u1, u2, u3}
1/ 2   −1/ 48   −2 / 3
     −1/ 3 
u1 =  0  , u 2 =  4 / 48  , u3 =  
1/ 2     2 / 3 
   1/ 48 

– Finally, we have A=UDUT with

1/ 2 -1/ 18 -2 / 3  7 0 0 
  0 7 0 
=U = 0 4 / 18 -1/ 3 , D  
  0 0 -2 
1/ 2 1/ 18 2 / 3 

17
• Combining the two results above, we have the following:
• In general, an n´n symmetric matrix A can be expressed as
A=UDUT with U being an orthonormal matrix and D being a diagonal
matrix
• Notice that this is an amazing result. Without symmetric property,
we cannot guarantee a matrix can be diagonalized

• Another form of this diagonalization expression is

0 ... 0  u1  u1T 
T
λ1
0    T
λ2 ... 0  uT2   u2 
= = [u1 u 2 ... u n ] 
A UDU T
= [λ1u1 λ2u 2 ... λnu n ]  
      
  T   
0 0 ... λn  u n  u n 
T

A λ1u1u1T + λ2u 2uT2 + ... + λnu nuTn

=

• This is known as spectral decomposition

18
• Example: Construct a spectral decomposition of the matrix with the
following diagonalization:
7 2   2 / 5 -1/ 5  8 0   2 / 5 1/ 5 
=A =     
2 4  1/ 5 2 / 5   0 3  -1/ 5 2 / 5 

u1 u2
– We identify the eigenvalues and eigenvectors from the above
expression
– Then we can write= A 8u1u1T + 3u 2uT2
– To verify this expression, we compute
 2/ 5   4 / 5 2/5
= uu =
T
1 1
 
  2/ 5 1/ 5   
1/ 5   2/5 1/5 
-1/ 5  1/ 5 -2/5
= u 2uT2 =  -1/ 5 2/ 5 
2/ 5  -2/5 4/5 
– And 
 
  

 4 / 5 2/5 1/ 5 -2/5 7 2 

8u1u1T + 3u 2uT2 = 8 ×   + 3 × -2/5 4/5  =  2 4  = A
 2/5 1/5     
19
 Quadratic Forms
• A quadratic form on n is an expression of the form Q(x) = xTAx,
where A is a symmetric matrix (if not symmetric, what can we do?)
• Notice that in the quadratic form, x is the input vector and the output
is a scalar
T 4 0 3 -2 
• Example: Let x=[x1 x2]T. Compute x= Ax for i) A =  ; ii) A  
0 3  -2 7 
 4 0   x1   x1 
i. x Ax
T
= [ x1 x2 ]    =  [ 4 x1 3x2 ]  = 4 x12 + 3x22
 0 3 x
 2  x2 
3 -2   x1   x1 
ii. xT Ax =[ x1 x2 ]    =[ 3 x1 -2 x2 -2 x1 +7 x ]
2   =3 x1
2
− 4 x x
1 2 + 7 x2
2

-2 7   x2   x2 
– Notice that cross-product terms exist in ii), due to the non-zero off-
diagonal elements
• Example: For x in 3, and let Q(x) = 5 x1 + 3x2 + 2 x3 − x1 x2 + 8 x2 x3 . Write
2 2 2

this quadratic form as xTAx

20
 2 2 2
– The coefficients of x1 , x2 , x3 go on the diagonal of A
– On the other hand, to guarantee A is symmetric, the coefficients of xixj
for i¹ j must be split evenly between the (i,j)- and (j,i)-entries of A
– It can be easily checked that
 5 -1/2 0   x1 
Q
= (x) x=
T
Ax [ x1 x2 x3 ] -1/2 3 4   x2 
 0 4 2   x3 
• We see that in general, a quadratic form involves the cross-product
terms
• However, if we write the quadratic form as
xT Ax x=
= T
UDUT x (UT x)T D(UT x)  y T Dy
we see that the quadratic form is in terms of y now and involves no
cross-product terms
• The columns of U are called the principal axes

21
  1 -4   x1 
• Example: Transform x T
Ax = [ x1 x ]
2    x  into a quadratic form
 -4 -5  2
with no cross-product term
– First, we need to find the eigenvalues and eigenvectors of A
– They turn out to be (with eigenvectors normalized to have unit norm)
 2/ 5  1/ 5 
λ1 =
3 : u1 =
 ; λ2 =
−7 : u3 =
  (prove it yourself)
 −1/ 5   2 / 5 
– Introduce a new variable vector y=[u1 u2]Tx
3 0   y1 
– Then the quadratic form can be written as y Dy = [ y1 y2 ] 
T

0 -7  y 
  2
– To illustrate the relationship between these two quadratic forms, we
input x=[2 -2]T into the original quadratic form, we obtain
 1 -4   2  2
xT Ax =
[2 − 2] 
-4 -5   −2  [
= 10 2 ]  =
−2
16
    
– On the other hand, y is computed as
 2 / 5 − 1/ 5   2  6 / 5  Multiplication by UT
=y =    
 1/ 5 2 / 5   −2  3 / 5 
– Putting into the new quadratic form, we have
3 0   6 / 5 
y T Dy = [6 / 5 3 / 5]   
2 2
 = 3(6 / 5) − 7(3 / 5) = 16
0 -7  3 / 5  22
• The matrix A is
– Positive definite if Q(x)>0 for all x¹0
– Negative definite if Q(x)<0 for all x¹0
– Indefinite if Q(x) assumes both positive and negative values
• Extensions to the above definitions are
– Positive semidefinite if Q(x)³0 for all x¹0
– Negative semidefinite if Q(x)£0 for all x¹0
• In practice, it is difficult to check directly whether a matrix is positive
definite, negative definite or indefinite using the above definitions
• But we can write
Q(x= ) xT Ax= y T Dy= λ1 y12 + λ2 y22 + ... + λn yn2
• Therefore, the matrix A is
– Positive definite iff the eigenvalues are all positive
– Negative definite iff the eigenvalues are all negative
– Indefinite iff A has both positive and negative eigenvalues

• Guess what are the requirements on the eigenvalues for the positive
semidefinite and negative semidefinite matrices?
23
• Example: Is the matrix A with quadratic form
Q(x) = 3 x12 + 2 x22 + x32 + 4 x1 x2 + 4 x2 x3 positive definite?
– First, convert the quadratic form back to matrix expression:
3 2 0   x1 
Q
= (x) x= T
Ax [ x1 x2 x3 ]  2 2 2   x2 
0 2 1   x3 

– The eigenvalues of A are 5, 2, and -1 (derive it yourself)

– Therefore, the matrix A is indefinite
• Note that a matrix having all elements positive has no relation to A
being positive definite

24
 Max and Min of Quadratic Forms
• In many applications, we are interested in the problem
max{xT Ax : x = 1}
x
where A is a symmetric matrix
• We want to select an x such that the quadratic form is maximized
• The constraint in the norm of x is needed, otherwise the quadratic
form can be as large as you want
• Now express A=UDUT, the problem becomes
max{(UT x)T D(UT x) : x = 1}
x
• Let y=U x, and notice that ||y||=||UTx||=||x||, the problem can be
T

reformulated as
max{y T Dy : y= 1} ⇒ max{λ1 y12 + ...λn yn2 : y12 + ... + y=
2
n 1}
y y1 ,..., yn

• Without loss of generality, it is assumed that the eigenvalues are

arranged in descending order (i.e., from most +ve to most -ve)
• It is obvious that the solution of y is y = [1 0 … 0]T
25
• Then, x can be recovered by x = Uy = u1
• That is, the x that maximizes xTAx under unit norm constraint is the
(normalized) eigenvector corresponding to the largest eigenvalue of
A
• And the maximum value of xTAx equals its largest eigenvalue:
=λmax max{
= xT Ax : x 1}
x

• Similar derivation would give the following result:

=λmin min{
= xT Ax : x 1}
x

and the x that gives the minimum value of xTAx is the normalized
eigenvector corresponding to lmin
3 2 1
• Example: Let A =  2 3 1 . Find the maximum value of xTAx subject
 
1 1 4 
to the constraint xTx=1, and find a unit vector at which this maximum
value is attained.
26
 – The eigenvalues of A can be found by solving the characteristic
equation, which turns out to be (prove it)
0=−(λ − 6)(λ − 3)(λ − 1)
– So the maximum value of xTAx subject to the constraint xTx=1 is 6
– The corresponding eigenvector can be obtained by solving (A-6I)x=0
– The eigenvector is in the direction [1 1 1]T (derive it yourself)
– Normalizing the vector [1 1 1]T gives the maximizing
u1 = [1/ 3 1/ 3 1/ 3]T

• Application: (details not to be examined) In a communication system,

we have a useful signal u, but it is corrupted by noise v. We want to
design a filter w at the receiver such that the signal-to-noise ratio is
maximized.
Signal u Output y
– The output signal can be written as Filter w
= y w T (u + v )
Noise v
– Assume signal and noise are uncorrelated
– Also, the noise samples are also uncorrelated with each other
27
– The power of useful signal portion is
=Po 
=[(w T u)(w T u)T ] w T 
[uuT ]w  w T Rw
– The power for the noise portion is variance of
noise samples
= N o [(w T=
v )(w T v )T ] w=
T

[ vvT ]w σ 2 w T w
– We want to maximize the signal-to-noise power ratio
Po w T Rw 1 w T Rw
SNR=o = =
N o σ 2 w T w σ 2 || w ||2
– This problem is in fact equivalent to (the noise variance s2 is a constant,
so does not matter)
max{w Rw : w = 1}
T
w

– The solution of the optimal w is thus the eigenvector corresponding to

the largest eigenvalue of the R matrix

28