finals: sections 5.9 - 7.4

Question 1

what is a probability vector?

Answer 1

a vector with nonnegative entries that add up to one

Question 2

what is a stochastic matrix?

Answer 2

a square matrix that holds probability vectors

Question 3

what is a markov chain?

Answer 3

a sequence of probability vectors such that
x1 = Px0, x2 = Px1, …., where xk+1 = Pxk

Question 4

what is a steady state vector?

Answer 4

a probability vector for a stochastic matrix P such that Pq =q

Question 5

if P is a stochastic matrix, then ______________

Answer 5

1 is an eigenvalue of P

Question 6

when is a stochastic matrix regular?

Answer 6

if there exists a positive integer k such that P^k has strictly positive entries

Question 7

what is the dot product (inner product) of two vectors?

Answer 7

u^T * v

Question 8

what is a unit vector?

Answer 8

a vector of length 1

Question 9

why do we care about orthogonal basis?

Answer 9

the weights can be computed easily

Question 10

why are orthonormal matrices important in computer algorithms?

Answer 10

for matrix computations

Question 11

an mxn matrix has orthonormal columns if and only if ________

Answer 11

U^T * U = I

Question 12

what is an orthogonal matrix?

Answer 12

a square matrix U such that U^T = U^-1 and U has orthonormal columns <– implied by saying U is an orthogonal matrix

Question 13

what are the properties of the dot product?

Answer 13

1) u (dot) v = v (dot) u
2) (u + v) (dot) w = u (dot) w + v (dot) w
3) (cu) (dot) v = c(u (dot) v) = u (dot) (cv)
4) u (dot) u >= 0, u (dot) u = 0 if and only if u = 0

Question 14

what is the definition of the length (or norm) of a vector?

Answer 14

||v|| = √(v * v) = √(v1^2 + v2^2 + … Vn^2)
and
||v^2|| = v * v

Question 15

for u and v in R^n, the distance between u and v, written as dist(u, v) is the length of the vector u - v. That is, ______________

Answer 15

dist(u, v) = ||u - v||

Question 16

when are two vectors orthogonal to each other?

Answer 16

when their dot product equals zero

Question 17

two vectors are orthogonal to each other if and only if (use Pythagorean theorem) __________

Answer 17

||u + v||^2 = ||u||^2 + ||v||^2
if the length of (u + v)^2 is equal to the length of u squared plus v squared

Question 18

if S + {u1, …, up} is an orthogonal set of nonzero vectors in R^n , then S is ____________

Answer 18

linearly independent and a basis for the subspace spanned by S

Question 19

what is an orthogonal basis for W?

Answer 19

it is a set of vectors that are orthogonal and are also a basis for W

Question 20

what is an orthonormal set?

Answer 20

an orthogonal set of all unit vectors

Question 21

an mxn matrix has orthonormal columns if and only if ____________

Answer 21

U^T*U = I

Question 22

what is a symmetric matrix?

Answer 22

a matrix A such that A^T = A

Question 23

if A is symmetric, then any two eigenvectors from different eigenspaces are ______________

Answer 23

orthogonal

Question 24

an nxn matrix A is orthogonally diagonalizable if and only if ____________

Answer 24

A is symmetric

Question 25

what is orthogonally diagonalizable?

Answer 25

A = PDP^-1, but since a is orthogonal, P^-1 = P^T so
A = PDP^T

Question 26

when is the length of Axk maximized?

Answer 26

when x = v1, the eigenvector corresponding to the largest eigenvalue

Question 27

what is the definition of the singular value decomposition?

Answer 27

let A be an mxn matrix with rank r, then there exists an mxn matrix Σ for which the diagonal entries in D and the first r singular values of A, and there exists an mxm orthogonal matrix U and an nxn orthogonal matrix V such that A = UΣV^T

Question 28

is the SVD, are U and V unique?

Answer 28

no

Question 29

what are the singular values of a matrix A?

Answer 29

the square roots of the eigenvalues of A^T * A

Question 30

which matrix factorizations always exist for any matrix?

Answer 30

SVD ONLY