Midterm 3 Flashcards
Diagonal matrix
matrix where the only non-zero entries are on the diagonal
similar matrices
a matrix A is similiar to a matrix D if A = PDP^-1
P is an invertible matrix
A and D have the same eigenvalues and determinants!!!
- they have the same characteristic polynomial and therefore the same eigenvalues
If two matrices have the same eigenvalues, does that necessarily mean they are similar to each other?
FALSE, only the converse is true
Diagonalization
Splitting up matrix A into a diagonal matrix D and an invertible matrix P
- very useful for computing A^k with large ks
A^k = PD^kP^-1
Algebraic multiplicity
the number of repeats for an eigenvalue
Geometric multiplicity
the number of eigenvectors for a given eigenvalue
Dimension of the Null(A- λI) for a specific λ
Singular
NOT INVERTIBLE
free variables, linearly dependent columns
Nonsingular = invertible!
Diagonalization Formula
A = PDP^-1
P: set of all linearly independent eigenvectors
D: the corresponding eigenvalues (in order)
Allows us to solve A^k for large k
A^k = PD^kP^-1
The Diagonalization Theorem
An nxn matrix A is diagonalizable if and only if A has n linearly independent eigenvectors
Dimension of A = Dimension of P
A is diagonalizable if and only if there are enough eigenvectors to form a basis of Rn : eigenvector basis
Steps to Diagonalize a Matrix
- find the eigenvalues using the characteristic polynomials
det(A - λI) = 0 - find the linearly independent eigenvectors of A
(A - λI)v = 0, plug in λ
- solve the null space in parametric vector form
IF the number of total eigenvectors is NOT equal to the number of columns in A, then A is not diagonalizable - Construct P from the eigenvectors
- Construct D using the corresponding eigenvalues
Theorem - Eigenvalues and Diagonalizable
An nxn matrix with n distinct eigenvalues is diagonalizable
- if vi …vn are eigenvectors correspond to n distinct eigenvalues of matrix A. Then {vi … vn} is linearly independent, therefore A is diagonalizable
BUT it is not necessary for a nxn matrix to have n distinct eigenvalues to be diagonalizable
Theorem - Matrices whose Eigenvalues are Not Distinct
Geometric multiplicity must be less than or equal to algebraic multiplicity of λ
A matrix is diagonalizable IF AND ONLY IF the sum of the dimensions of the eigenspaces (Nul(A -λI)) equals n (the number of columns)
Total geometric multiplicity = number of columns in matrix A THEREFORE geometric multiplicity has to equal algebraic multiplicity
characteristic polynomial of A factors completely into linear factors - can be real or imaginary
DIAGONALIZABILITY AND INVERTIBILITY
they have no correlation with each other
-a matrix can be diagonalizable but not invertible because it can have a eigenvalue of 0
- a matrix can be invertible but not diagonalizable
1,1
0,1
Complex number
a + bi
i = sqrt(-1)
Complex eigenvalue
eigenvalue that is a complex number a + bi
if b = 0, then λ is a real eigenvalue
Complex eigenvector
an eigenvector subsisting of a complex eigenvalue
Complex number Space ℂn
the space of all complex numbers
ℂ2
complex number space with 2 entries
at least one entry is a complex number
Conjugate of a complex number
the conjugate for (a+bi) is (a-bi)
Complex conjugate of a vector x
x with a bar on top of it
Re x
the real parts of a complex vector x
an entry CAN be 0
Im x
the imaginary parts of a complex vector x
an entry can be 0
We can identify ℂ with R2
a + bi <-> (a,b)
we can add and multiply complex numbers
Add: like normal (2-3i)+(-1+i) = 1-2i, similiar to matrix addition
Multiply: FOIL!!! - no matrix multiplication
absolute value of a complex number a + bi
sqrt(a^2 + b^2)
we can write complex numbers in polar form
(a,b) = a + ib = r(cosφ + isinφ)
a is the real part and b is the imarginary part
Argument of lambda = a + bi
the angle φ produced by a and b on their respective Re x and Im x axis
Finding complex eigenvalues and complex eigenvectors
- det(A - λI) = 0 to get the eigenvalues λ; the complex roots are the complex eigenvalues
- Solve (A-λI)x = 0 for x to get the eigenvectors
should get one “free variable” - Find the other eigenvector
- Find the conjugate of the other eigenvector!
Re x and Im x
xbar = vector whose entries are the complex conjugates of the entires in x
for example:
(3-1,i, 2) => (3,0,2) + i(-1,1,0)
Re x is the first, Im x is the second
xbar = (3+i,-i,2)
Properties of Complex Conjugate Matrixes
you can find the conjugates first and then multiply together for:
rx Bx BC rB ???
r being scalars
uppercase being matrixes and x being vectors
conjugate of (x + y) = xbar + ybar
conjugate of Av is equal to Avbar
Im(xxbar) = 0
(xy)bar = xbarybar
Complex Eigenvalues and Complex Eigenvector Come in Pairs!!!
no such thing as an odd number of complex eigenvalues
Rotation Dilation Matrix
matrix in the form of
a,-b
b,a
the eigenvalues are: a + bi, a - bi
the length of the eigenvalue (r) is sqrt(a^2+b^2)
the angle of the eigenvalue is tan^-1(b/a)
Euler’s Formula
e^(iφ) = cosφ + isinφ
multiplying two complex numbers =
r1*r2e^(i(φ1+φ2))
Complex numbers and Polynomials
if lambda is a complex root of characteristic polynomial, then lambda bar is also a root of that real polynomial
lambda bar is an eigenvalue of A as well with an eigenvector of vbar
Inner Product or Dot Product
a scalar
u*v
uTv
Vector Length
||v|| = sqrt(v*v) = sqrt(v1^2 + v2^2 +…+vn^2)
Unit Vector
vector whose length is 1
Vector normalization
Dividing a nonzero vector by its length to make it a unit vector
(1/||v||)*v
Distance between two vectors
dist(u,v) = || u - v||
Orthogonal vectors
Two vectors are orthogonal if their dot products equals 0
Orthogonal complements
A set of vectors that are all orthogonal to a subspace W
Representation as a line or plane depends on the nullspace of W
For a subspace to be in Rn
subspace (contains the zero vector and is closed under addition and multiplication) has n entries for each vector in it (dimension n)
R1 means that the vectors have one entry
Span of just [1]
Dot Product vs Cross Product
dot product gives you a number while cross product gives you a vector
Theorem: Dot Product Properties
uv = vu (Symmetry)
(u + v) * w = uw+ vw (linearity) and vice versa
c is a scalar:
(cu)v = c(uv) = u * (cv)
- can find the dot product of the two vectors first and then multiply by the scalar
uu >= 0 (Positivity!)
uu = 0 only if u = 0
Vector Length Properties
vector length is always positive
||cv|| = |c| ||v||
||cv||^2 = c^2 ||v||^2
Normalizing a Vector
v(1/||v||) gives u, a unit vector
u is in the same direction as v BUT it has a different magnitude (because the length changed)
Finding the Distance between Two Vectors
- subtract the two vectors (u-v)
- find the length of the resultant vector
|| u - v ||
Orthogonality Basics
Two vectors are orthogonal = two vectors are perpendicular to each other
||u - (- v) || = || u - v ||
u * v = 0
Zero vector is orthogonal to every vector in Rn
The Pythagorean theorem
two vectors are orthogonal if and only if || u + v||^2 = ||u||^2 + ||v||^2
Orthogonal Complements Basics
set of vectors where each vector is orthogonal to a subspace W
Orthogonal COmplement of W = W⊥
W⊥
a vector x is in W⊥ if and only if x is orthogonal to every vector in a set that spans W
- must calculate every single dot product pair to prove orthogonality
W⊥ is a subspace of Rn just like W
- both subspaces have n entries
- do not necessarily have the same dimension
dim(Row W⊥) = n - dim(Col W)
because Row W⊥ = Nul W
Theorem: Perps of SubSpaces
Let A be an mxn matrix:
(Row A)⊥ = Null A
(Col A) ⊥ = Null A^T
Proof:
Av = 0
- taking the dot product of every row of A with the vector v and seeing if v is orthogonal to A = dot product of every row of A is equal to 0 making the vector v orthogonal to A which is also the null space of Av = 0
Rank Theorem Expanded and Row A
Row A: space spanned by the rows of matrix A
pivot rows of A
dim(Row A) = dim(Col A)
# of pivot rows is equal to the number of pivot columns
Row A^T = Col A
THEREFORE N (number of columns in a matrix)
Dim(Col A) + dim (Nul A) = N
Dim(Row A) + dim(Nul A) = N
Orthogonal Set
~~~
```a set of vectors in Rn where each pair of distinct vectors from the set is orthogonal
ui*uj = 0 where u and j don’t equal each other
Orthogonal Basis
basis for a subspace W that is also an orthogonal set
Orthogonal Projection
projecting a vector onto a line/plan to get its orthogonal complement?
yhat = proj(_L)y =
(yu/uu)u
With L being the subspace spanned by u
(subspaces must include the 0 vector)
Orthonormal set
orthogonal set where every vector is a unit vector
Orthonormal basis
basis for a subspace W that is also an orthonormal set
Orthogonal Matrix
SQUARE matrix whose columns form an orthonormal set
Theorem: Orthogonal Sets and Linear Independence
if S = {u1…up} is an orthogonal set of nonzero vectors in Rn, then S is linearly independent and is a basis for the subspace spanned by S
All Orthogonal Sets are Linearly Independent Sets
TRUE only if there are no zero vectors
BUT not all linearly independent sets are orthogonal
REMEMBER to omit the zero vector for an orthogonal set!
Theorem: Finding the weights for a linear comibination of an orthogonal basis
Let {u1…up} be an orthogonal basis for a subspace W or Rn
for every y in W, the weights in the linear combination
y = c1u1+…+cpup
is given by
cj = (yuj/ujuj)
FOR ORTHOGONAL BASES
How to find an Orthogonal Projection
yhat = proj(L)y = (yu/uu)u
y = yhat + z (z is the component of y orthogonal to u)
Orthogonal Projections can be written as a Linear Combination of a Vector’s Components
y = (yu1/u1u1)u1 + (yu2/u2u2)u2
Orthonormal Sets vs Orthogonal
all orthonormal sets are orthogonal while not all orthogonal sets are orthonormal
Theorem: Transpose of matrix with Orthonormal Columns
A mxn matrix U has orthonormal columns if and only if U^TU = I
-the transpose of a matrix with orthonormal columns multiplied by the original matrix ALWAYS results in the identity matrix (even if NOT square!)
Proof: an orthonormal vector times itself is the square root of its length which is 1 (dot product)
A^TA where A is a matrix with orthogonal columns
produces a diagonal matrix with all entries equal to each vector’s length squared
Theorem: Properties of a Matrix with orthonormal columns
||Ux|| = ||x||
linear mapping x -> Ux preserves length
(Ux)(Uy) = xy
(Ux)*(Uy) = 0 if and only if x and y are orthogonal to each other
- preserves orthogonality
Difference between Orthogonal Matrix and a Matrix with Orthonormal Columns
Orthogonal Matrices must be square
● U-1 = UT
○ The inverse of orthogonal matrices is its transpose
○ Orthogonal matrices have linearly independent columns
Determinant of an Orthogonal Matrix
if A is an orthogonal matrix, then detA is equal to 1 or -1
converse is NOT TRUE
Orthogonal Projection vs orthogonal component of y onto W
yhat vs z
z = y - yhat
Best Approximation
||y-yhat|| < ||y - v||
the verticle distance going straight up and down between a vector and its projection space
ANY distance between a vector and a subspace that is not per pendicular to the space is automatically not the shortest distance
Properties of an orthogonal projection onto Rn
Given a vector y and a subspace W in Rn, there is a vector yhat in W that is the UNIQUE vector in W for which y-yhat is orthogonal to W
yhat is the unique vector in W closest to y
Theorem: Orthogonal Decomposition Theorem
Let W be a subspace of Rn; each y in Rn can be written uniquely in the form of y =yhat + z whre yhat is in W and z is in Wperp
if {u1..up} is any orthogonal basis of W then yhat is
the fun equation we all know about
we assume that W is not the zero subspace because everything projected on the zero subspace is just the zero vector
Properties of Orthogonal Projections
if y is in W = Span {u1…up} then projwy = y
if y is already in the subspace then projecting it onto the same subspace does nothing
The Best Approximation Theorem
||y-yhat|| < ||y-v||
yhat is the closest point in W to y
Theorem: Orthonormal Basis and Projections
if {u1….up} is an orthonormal basis for a subspace W in Rn, then proj = (y*u1)u1 + (y *u2)u2…
projwy = UU^Ty for all y
Theorem: Matrix with orthonormal columns vs orthogonal matrix
if U is an nxp matrix with orthonormal columns and W is the column space of U, U^TUx = Ipx = x for all x in Rp
UU^Ty = projxy for all y in Rn
if U is an nxn matrix with orthonormal columns then U is an orthogonal matrix
UU^Ty = Iy = y for all y in Rn
Gram-Schmidt
producing an orthogonal/orthonormal basis for any nonzero subspace of Rn
The actual algorithm for Gram-Schmidt
v1 = x1
v2 = x2 - (x2 *v1/v1 *v1)v1
v2 = x3 - (x3 *v1/v1 *v1)v1 - (x3 *v2/v2 *v2)v2
…
{v1…vp} is an orthogonal basis for W… what about its Span in relation to original matrix
Span are the same
span{v1..vp} = span{x1..xk}
what is required for gram-schmidt
linearly independent basis
any nonzero subspace has an orthogonal basis because an ordinary basis {x1..xp} is always available
Orthonormal Bases
normalize all vectors in the orthogonal basis
QR Factorization
If A is an mxn matrix with linearly independent columns, then A can be factored as A = QR
Q: an mxn matrix whose columns form an orthonormal basis for Col A
R: an nxn upper triangular invertible matrix with positive entires on its diagonal
How to QR Factorize
Use Gram-Schmidt to find Q, if needed, normalize to make it orthonormal
THEN solve A = QR or solve R = Q^TA
if the columns of A were linearly dependent, then R would not be invertible
General least-squares problem
Finding the x that makes ||b-Ax|| as small as possible
Normal Equations
A^TAx = A^Tb
Difference between x and xhat
x just refers to some general solution while xhat is the solution that solves the least squares problem/normal equations
least squares error
distance from b to Axhat where xhat is the least-squares solution to b
||b-Axhat||
why do we solve least-square problems
want to find a close enough solution to Ax = b when it is an inconsistent system
if A is mxn and b is in Rn, a least-squares solution of Ax=b is an xhat in Rn such that
||b-Axhat|| <= ||b-Ax|| for all x in Rn
it can be equal when the columns of A are linearly dependent?
if A is already consistent, then ||b-Axhat|| = 0
Solution of the General Least-Squares Problem
Use normal equations!!
Theorem: Least Square Solutions and Normal EQ
set of least-squres solutions of Ax=b coincide with the nonempty set of solutions of the normal equations A^TAx = A^Tb
POSSIBLE TO HAVE more than one least-squares solution
- with the existence of a free variable aka columns of A are linearly dependent
Theorem: Logically equivalent statements
- the equation Ax = b has a unique least-squares solution for each b in Rn
- the columns of A are linearly independent
- the matrix A^TA is invertible
When these statements are true, the least-squares solution xhat is given by xhat = (ATA)^-1ATb
Least Squares Error
||b-Axhat||
Theorem: Finding the LeastSquares Solution using QR Factorization
given an mxn matrix A with linearly independent columns, let A = QR be aQR factorization
the equation Ax = b has a unique least-square solution, given by
xhat = R^-1Q^Tb
Rxhat = Q^Tb
if b is orthogonal to the columns if A, what can we say about the leastsquares solution
if b is orthogonal to A, then the projection of b onto A is 0
a least square solution xhat of Ax=b satisfies Axhat = 0
Least-Squares Lines
y = B0 + B1x
Residual
the difference between the actual y-value and the predicted y-value
Least-Squares Line
line of best-fit for a set of data
minimizes the sum of the residuals aka the least-squares solution
Objective in Least-Squares Lines
finding B0 and B1 that create the least-squares lines, plugging in xs from the data points
using Betas as your variables
can use the normal equations to solve
Mean-Deviation Procedure
- find the average of all the x-values x_
- calculate x* = x - x_
- then solve XB = y but use the x* values
General Linear Model
y = XB + episolon
solve the normal equations
XTXB = XTy
