MATH 315 Exam 1

Ax=b

a matrix that contains only the coefficients of a system of equations

a coefficient matrix with an extra column containing the constant terms

a system of equations or inequalities that has no solution

a matrix that contains the constants of a system

A square triangular (upper or lower) matrix with 1s on the main diagonal, but it can have non-zero values above or below the main diagonal

1. (Replacement) Replace one row by the sum of itself and a multiple of another row.
2. (Interchange) Interchange two rows
3. (Scaling) Multiply all entries in a row by a nonzero constant

An invertible matrix that results by performing one elementary row operation on an identity matrix

a column containing a pivot position

Gaussian elimination succeeds using only row operations of type "add a multiple of one row to a lower row" (equivalently, with n nonzero pivots, no row swaps)

If A=LU where U is upper triangular and L is lower triangular with 1s on the diagonal, then the product is called an LU factorization of A.

a matrix that is invertible

A=LDV with D diagonal, V upper unitriangular

Ax=0

a square matrix is regular iff it has an LU factorization with nonzero diagonal in U; the factorization is unique; the entries of L below the diagonal are multiplers used in elimination

A is nonsingular iff A has n pivots iff Ax=0 has only x=0 iff Ax=b has a unique solution for every b iff A^-1 exists iff detA=/= 0

if A is symmetric and regular then A=LDL^T (so V=L^T)

det(AB)=detAdetB; detA^T=detA; detA^-1=1/detA; the determinant of a triangular matrix is the product of its diagonal entries; detA is the product of the pivots

many axioms, including closure under addition and scalar multiplication, zero vector, additive inverses

A subset of a vector space that is also a vector space.

Set of all linear combinations of the basis vectors

A set of vectors that has only the trivial solution (They are not linear combinations of any of the other vectors). A has a pivot in every column.

If a vector is a linear combination of any vector or combination of vectors in a set, then it is linearly independent. If a vector in a set is removed and the span is the same, then the set was linearly dependent. If the set contains the zero vector, it is linearly dependent. If the matrix has a free variable, then it is also linearly dependent

a set of vectors that is linearly independent and spans the space

the number of vectors in a basis for V

the set of all input vectors that result in the zero vector when multiplied by the matrix

the set of all possible output vectors that can be reached by plugging in vectors from the domain

the set Col A of all linear combinations of the columns of A

the quotient space of the domain V by the kernel of T

the quotient space or quotient group Y / im(f) of the codomain Y by the image of f

the set of all solutions of the homogeneous equation Ax=0

W⊆V is a subspace iff 0∈W and W is closed under addition and scalar multiplication

intersections are subspaces
unions are generally not

v1,...,vk ∈Rn are independent iff the matrix with these columns has K(A)={0} (rank k)

-every basis of V has the same number of elements
- in an n-dimensional space, any n independent vectors form a basis, and any n spanning vectors form a basis
- any idenpendent set extends to a basis
-any spanning set contains a basis
- A proper subspace of V has strictly smaller dimension

- pivot columns of A give a basis for I(A)
- nonzero rows of an echelon form give a basis for Iv(A)
- free variables parametrize K(A)
-K∨(A) is the kernel of AT

- the dimension of the domain (or the number of columns) is equal to the sum of the rank and the nullity
- dim I(A) = dim I ∨(A) = rank A = r
- dim K(A) = n − r
- dim K v (A)=m-r
- also, rankA= rankA^T

if Ax1 = b1, Ax2 = b2 then A(c1x1 + c2x2) = c1b1 + c2b2. Consequently Ax = b is solvable iff b ∈ I(A).

- dim(row space) = r
- dim(column space) = r
- dim(nullspace) = n-r
- dim(left nullspace) = m-r

symmetric, bilinear, postive definite

inner product =0

sqrt(inner product v)

A vector with a magnitude of 1 (vector divided by its norm)

making the vector a unit vector: v*(1/||v||)

symmetric with x^TKx > 0 for all x=/= 0

The Gram Schmidt process is used to transform a set of linearly independent vectors into a set of orthonormal vectors forming an orthonormal basis. It allows us to check whether vectors in a set are linearly independent.

Kij = (inner product vi,vj)

K=MM^T, M lower triangular with positive diagonal

| inner product v,w | ≤ ||v|| ||w||, with equality iff v, w are parallel

v ⊥ w then ∥v + w∥ ^2 = ∥v∥ ^2 + ∥w∥ ^2 .

cos θ = ⟨v, w⟩/(∥v∥∥w∥)

⟨v, w⟩ = v T Kw with K symmetric positive definite

a symmetric matrix is positive definite iff it is regular with all pivots positive iff K = LDLT with D > 0 iff it has a Cholesky factorization. For 2 × 2: a b b c is positive definite iff a > 0 and ac − b 2 > 0

orthogonal matrix Q (Q^TQ = I, i.e. Q^−1 = Q^T )

QR factorization A = QR (Q with orthonormal columns, R upper triangular)

H = I − 2uu^T for a unit vector u

W⊥ = {v : ⟨v, w⟩ = 0 ∀w ∈ W}

the unique w ∈ W with v − w ∈ W^⊥

nonzero, mutually orthogonal vectors are linearly independent

if u1, . . . , un is orthonormal, then v = P⟨v, ui⟩ui and ∥v∥ 2 = P⟨v, ui⟩ 2 (Parseval); for an orthogonal basis, v = Summation (⟨v,vi⟩/ ∥vi∥^2) vi .

wk = vk - Summation (⟨vk,wj⟩/ ∥wj∥^2) wj
with span{w1...wk}=span{v1...vk}
Its equivalent to A=QR with rii>0

- the columns (and rows) are orthonormal
- products and inverses of orthogonal matrices are orthogonal
- det Q = ±1
- ||Qx|| = ||x|| and QxQy=xy
- Householder matrices are symmetric, orthogonal, and satisfying H^2 =I

A factorization of an m x n matrix A with linearly independent columns,
A = QR, where Q is an m x n matrix whose columns form an orthonormal basis for Col(A), and R is an n x n upper triangular invertible matrix with positive entries on its diagonal.
Ax=b becomes Rx=Q^Tb

for v=/= w with ||v||=||w||, H built from u=(v-w)/||v-w|| satisfies Hv=w and Hw=v
Used to triangularize A column by column

K(A) = (I^∨(A))^⊥ and K^∨(A) = (I(A))^⊥ in Rn and Rm respectively; so Rn = K(A)⊕I^∨(A) and Rm = I(A)⊕K^∨(A).

then (W^⊥)^⊥=W

least squares solution x⋆ of Ax = b (minimizes ∥Ax − b∥)

b-Ax

A^TAx=A^Tb

the point of W nearest to b is the orthogonal projection v of b; b − v ⊥ W and ∥b−v∥ ≤∥b−w∥ for all w ∈W.
If W =I(A) has basis the columns of A (independent), the projection is A(ATA)−1ATb (with respect to the dot product).

x⋆ minimizes ∥Ax−b∥ iff it solves the normal equations; the normal equations are always consistent; the solution is unique iff K(A) = {0}, in which case x⋆ = (A^TA)^−1A^Tb. For a weighted inner product with weight matrix C: A^TCAx = A^TCb

thus, A^TA is invertible iff A has independent columns

the minimal squared error is ∥b∥2−∥Ax⋆∥2.