Definitions

Question 1

What is a Vector Space?

Answer 1

A Vector Space over a field K is a triplet consisting of a set of vectors, a vector addition and a scalar multiplication which stisfies the folloeing rules:
1. Closure of +: u + v in V
2. Closure of : av in V
3. Associativity of +: (u + v) + w = u + (v + w)
4. Associativity of : a(bv) = (ab)v
5. Commutativity of +: u + v = v + u
6. Commutativity of : (a + b)v = av + bv
7. Distribution of vectors over scalar: a(u + v) = au + av
8. Existence of zero vector s.t 0 + v = v
9. Existence of inverse additive vector: u + (-u) = 0
10. Multiplicative identity satisfies 1v = v

Question 2

Give the definition of a distance function on a vector space.

Answer 2

A distance function is a map d: VxV -> [0, inf[ s.t:
1. d(u,v) >= 0 and d(u,v) = 0 iff u=v
2. d(u,v) = d(v,u)
3. d(u,w) <= d(u,v) + d(v,w) (triangle inequality

Question 3

What is a metric vector space?

Answer 3

A metric vector space is a vector space equipped with a distance function.

Question 4

Give the definition of a norm.

Answer 4

A Norm on a vector space is a map ||||: V -> [0, inf[ st:
1. ||u|| >= 0, ||u|| = 0 iff u = 0
2. ||Av|| = |a|*||u||
3. ||u + v|| <= ||u|| + ||v||

Question 5

What is the definition of an inner product?

Answer 5

An inner product on a V.S is a map <,>: VxV -> R st:
1. <u,v> = <v,u>
2. <au,v> = a<u,v>
3. <v + w,u> = <v,u> + <w,u>
4. <v,v> >=0 and is equal to zero iff v=0

Question 6

What is the definition of a subspace?

Answer 6

W in V is a subspace iff:
1. Closure under +
2. Closure inder *
3. 0 vector is a part of W

Question 7

What is the definition of a linear combination?

Answer 7

A Linear combination of a se of vectors is an expression of the form: a1v1 + a2v2 + … + an*vn = v

Question 8

What is the definition of the span of a set s in V?

Answer 8

Span(s) = [a1s1 + … + ansn | an in R and sn in S]. It is the set of possibilities that can be reached by linear combinations of the vectors in set S.

Question 9

How can we determine if a set of vectors is independent?

Answer 9

If the linear combination of the set is equal to zero iff a1, …, an are all equal to zero.

Question 10

What is the Basis of a Vector Space?

Answer 10

B in V is a Basis if:
1. Span(B) = V
2. B is independent.

Question 11

What is the definition of the Dimension of a V.S?

Answer 11

The number of elements in a basis of a vector space is a called the dimension, Dim(V).

Question 12

What is the matematical definition of two orthogonal vectors?

Answer 12

<u,v> = 0

Question 13

What is the definition of a Projection of u onto v?

Answer 13

Proj.v(u) = (<u,v> * v)/<v,v>

Question 14

What is the Cauchy-Schwartz Theorem?

Answer 14

<u,v>^2 <= <u,u> * <v,v>
or
|<u,v>| <= ||u||*||v||

Question 15

What is the definition of an angle between two vectors?

Answer 15

cos(theta(u,v)) = <u,v>/(||u||*||v||)

Question 16

What is the definition of a Linear Transformation ofver a vector Space?

Answer 16

A Linear Trasformation is a function T: V –> W which must satisfy:
1. T(v1 + v2) = T(v1) + T(v2)
2. T(av1) = aT(v1)

Question 17

What is the Null space of a Linear Transformation?

Answer 17

Given a Linear Transoframtion T: V –> W, the Null Space or the Kernell of T as the set of elements in v that map t the zero vector :
N(T) = {v in V: T(v) = 0}

Question 18

What is the Image of T?

Answer 18

The image is the span of Vectors of the Linear Transformation.
Im(T) = {w = T(v): v in V}

Question 19

What is the nullity of the linear transformation T: V –> W?

Answer 19

The nullity is the dimension of the Null space.
Note that Dim(V) = Null(T) + rank(T)

Question 20

Give the definition of an Orthogonal Matrice? What characteristics does it preserve when used as a Linear Transformation?

Answer 20

An orthogonal matrice Q is a matrice with orthonormal columns. That is, its columns are both orthogonal and of norm 1. It preserve:
1. Inner product s.t (Qu)^T * (Qv) = u^Tv = <u,v>
2. Norms s.t ||Qu|| = ||u||
3. Angles

Question 21

What is the Definition of a Full QR Decomposition?

Answer 21

Given A = [a1, a2, … an] a Matrix mxn, full column rank, the Full QR decomposition A=QR is the extension of the Reduced Form s.t

[a1, a2, … an] = [q1, …, qn, qn+1, … ,qm][ r11, … r1n]
{Complmts} [ … … … ]
[ … … rnn ]
[0 … 0 ]
We can write A = QR +Q^c*[0]

Question 22

Name some properties of orthogonal matrices.

Answer 22

1. Preserves Inner product
2. Det(Q) = +-1
   Proof: 1 = Det(I) = Det(Q^TQ) = Det (Q)^2 s.t sqrt(1) = Det(Q)
3. Inverse of Q is orthogonal since Q^T = inverse of Q
   Note that Q =/= Q^T

Question 23

What is the Definition of a Given’s Matrice?

Answer 23

A Givens Matrix is of the form [c -s]
[s c] s.t c^2 +s^2 = 1

Question 24

What is the definition of a Householder Matrix

Answer 24

A Householer matrix corresponding to a vector v is defined by Hv = I - 2vv^T/(V^T*V)

Question 25

What is a Regression?

Answer 25

Regression refers to the collection of techniques for describingor capturing the dependencies btw different datasets using a certain functional relationship. Regression usually finds the best fit for that functional relationship through parameters. Best fits can be anything really, for example, minimizing th mean squared error which is the Norm L-2, but we could minimize the absolute value.

Question 26

Describe what a Singular Value Decomposition is.

Answer 26

The SVD allows us to break down the action of a Matrix A on vectors as a sequence of simpler steps being:
1. Reflection/Rotation in the Domain R^m
2. Scaling
3. Reflection/ Rotation in the image space R^n
Contrary to eigenvalue decomposition, SVD always exists, if A is real, so is its SVD.

Question 27

Describe the 3 matrices of the SVD decomposition

Answer 27

The middle matrice Sigma is a diagonal matrix of ordered singular values. V is a matrix of right singular vectors and U is a matrix of left singular vecotrs, both orthogonal matrices.

We can represent the singular Value Decomposition in this way:

A = Sum(sigma_iui*v_i^T). And so A, seen as a linear transformation, is a regroupement of of weighted sums of simpler linear transformations u_i(v_i^T). So the singular value associated with its corresponding left and right singular vector gives the importance of those within the whole transformation.

Question 28

What is de definition of a Matrix norm?

Answer 28

The induced matrix norm on A is ||A|| = max ||Ax||/||x||
or
when ||x|| = 1, max ||Ax||
In other words, it is the maximum stretch/scaling that a Matrix A can apply on a vector x.

Question 29

What is the Definition of an Eigenvalue?

Answer 29

An eigenvalue is a scalar “a” s.t there exists a non-zero vector called an eigenvector satisfying Av=av. In other words, an eigenpair of A is a pair of a scalar and a vector where the effect of A on the eigenvector can be simplified by a simple scaling by the eigenvalue.

An eigenbaiss is a basis where the action of A on any vector within its span can be interpreted as a linear combination of the basis and the eigenvalue.

Question 30

What is the Definition of an Characteristic Polynomial.

Answer 30

The characteristic polynomial of A is defined as det(A-I*“lambda”), whose roots are the eigenvalues of A.

Question 31

What is the definition of Algebraic Multiplicity?

Answer 31

The algebraic multiplicity of an eigenvalue is the value of its corresponding exponent in the characteristic polynomial.

Question 32

What is the definition of Geometric Multiplicity?

Answer 32

For a given eigenvalue of A, the geometric multiplicity is the number of distinct, linear independent vectors corresponding to the eigenvalue. Equivalently, the dimension of the underlying eigenspace.

Question 33

What is the definition of a Defective Matrix?

Answer 33

A Matrix is defective if the algebraic multiplicity of at least one eigenvalue is higher than its geometric multiplicity.

Question 34

What is Diagonalization and which amtrix can be diagonalizable?

Answer 34

Matrices with a full set of linearly independent eigenvectors are diagonalizable. This means we can Package Av where v is and nxn matrix into a a multiplication of two matrices. One forming the basis of v and a square matrix with diagonals being A’s eigenvalues. I.e Av = vD, or
A = VD*inv(V)

Question 35

What is the definition of similar matrices?

Answer 35

A and B are similar if there exist a matrix X, invertible s.t B= XAinv(X). B and A share multiplicity and characteristic polynomial as well as eigenvalues, but not always eigenvectors.

Question 36

What is the definition of a positive definite matrix?

Answer 36

A matrix is positive definite if the eigenvalues are real and positive, or non-negative for semi-definite.
Pos.Def Matrices have equivalent Eigenvalue decomposition and Singular Value Decomposition.

Question 37

What is the mathematical definition of a symmetric matrix?

Answer 37

transpose of A = A

Question 38

Describe what is the eigendecomposition of a matrix.

Answer 38

Mathematically, A = QVinv(Q).
Q is a square matrix with columns the eigenvectors of A and V is the diagonal matrix with elemets corresponding to its eigenvalues.

Question 39

What is the mathematical definition of a unitary matrix?

Answer 39

A matrix A is unitary if A^TA = AA^T=A*inv(A)=I

Question 40

State the existence of full SVD theorem.

Answer 40

For A in the Real mxn space,
1. There exist U in R mxn orthogonal
2. Sigma = Diag(σ_1,σ_2, …σ_min(m,n)) s.t σ_1 >= σ_2 >= … >= σ_min(m,n) >= 0
3. V in R mxn is Orthogonal s.t

A = U * Sigma * V^T

Note, A = Sum (from k=1 to min(m,n)) σ_k * u_k * v_k^T

Question 41

What are the compponents of the SVD decomposition that are unique?

Answer 41

Singular values are unique, but the SVD is not. However, if Sigma is ordered, thus U and V as well, then the SVD is unique up to a sign.

Question 42

State Schur’s Factorization Theorem for square matrices.

Answer 42

For any square matrix A with complex entries, A can be expressed as:
A = Q * U * inv(Q)
Where Q is a unitary matrix and U is upper triangular. Note that U is similar to A, and U’s diagonal entries are its eigenvalues. All square matrices have a schur decomposition, but it is not always unique.

Question 43

State the LU decomposition of a non-singular matrix A.

Answer 43

The LU decomposition for a non-singular Matrix A is the multiplication of a Lower Triangular Matrix with an Upper Triangular Matrix s.t
A = LU.

Question 44

State the normal equations method for the least square problem.

Answer 44

r=b-Ax s.t A^T * r =0

Question 45

State the QR decomposition method for the least square problem.

Answer 45

.

Question 46

State the Power Iteration Method to find the highest eigenvalue.

Answer 46

.

Question 47

Describe what the shifted inverse power iteration is and what it is used for.

Answer 47

The Power iteration method can only find the largest eigenvalue. The inverse power method finds the smallest one. Say we thought that an eigenvalue was close to 1, then shifting the Matrix A by the identity matrix times the scalar, 1 in our case, would put the smallest eigenvalue close to zero. Using the inverse power iteration, we could find the value and recover the eigenvalue needed with the following formula.

Question 48

State Schur’s Decomposition Theorem.

Answer 48

Given any square complex matrix, there exist a Unitary Q and uppertriangular U s.t A=QUQ^h