🔢

Linear algebra

TagsMath
Created
Updated

Vector

Review of key ideas:

  1. A vector V in n-dimensional space has n components v1, v2, v3
  1. V+W = (v1+w1, v2+w2) and cv = (cv1, cv2)

Chapter 1.2.

Chapter 1.3

Chapter 2.1

Matrix

A matrix is a rectangular array (arrange a group of things in a particular way) of numbers or "entries".

The idea of Elimination

Elimination (It's a numerical method):

Ax=b ->

[(entry to eliminate*pivot) / (pivot)] - entry to eliminate ->

keep going to find all n pivots and the upper triangular U->

Ux=c -> Back substitution or breakdown

(U) Upper triangle allows back substitution.

Rules:

pivot = first nonzero.

The multiplier is l = (entry to eliminate) / (pivot) .

if pivot == 0, then you exchange. When breakdown (pivot == 0) is permanent, Ax=b has no solution or infinitely many.

Note 1:

We want to reduce, hence We subtract:

[ax -by = c] Row 1

[dx - ey = d] Row 2

Numerical Variables

c - d = (ax-by) - (dx-ey)

Note 2:

new row = Row 2 - Row 1*(entry/pivot)

= (dx-ey=d) - (ax-by=c) * (d/a)

is the same operation

Row 1 * d By d(ax-by) = dc

Row 2 * c By a(dx-ey) = ad

new row = d(ax-by) - a(dx-ey) = dc - ad

Elimination Using Matrices

Vandermonde matrix is a matrix with the terms of a geometric progression in each row.

Example: [1 1 1; 1 2 3; 1 4 9].

Rules for Matrix Operations

Graph or network has n nodes

Inverse matrices

Sparse matrix

In numerical analysis and scientific computing, a sparse matrix or sparse array is a matrix in which most of the elements are zero. By contrast, if most of the elements are nonzero, then the matrix is considered dense. The number of zero-valued elements divided by the total number of elements (e.g., m × n for an m × n matrix) is called the sparsity of the matrix (which is equal to 1 minus the density of the matrix). Using those definitions, a matrix will be sparse when its sparsity is greater than 0.5.

Hermitian, symmetric, triangular, tridiagonal, or bidiagonal

Elimination = Factorization: A=LU

(E32E31E21)A=U becomes A=(E211E311E321)U=LU(E_{32}E_{31}E_{21})A=U \text{ becomes }A=(E_{21}^{-1}E^{-1}_{31}E^{-1}_{32})U=LU

L is a lower triangular product of elimination inverse and it contains the numbers lijl_{ij}. i.e. We want to factor A, not U.

The key reason why A=LU:

 Row n of U =(Row n of A)l31(Row 1 of U)l32(Row 2 of U)...\text{ Row } n \text{ of U }=\text{(Row } n \text{ of A)}- l_{31}\text{(Row } 1 \text{ of U)}- l_{32}\text{(Row } 2 \text{ of U)}-...
Row n of A= Row n of U +l31(Row 1 of U)+l32(Row 2 of U)...\text{Row } n \text{ of A}=\text{ Row } n \text{ of U }+ l_{31}\text{(Row } 1 \text{ of U)}+ l_{32}\text{(Row } 2 \text{ of U)}-...

E+L=2I?E+L=2I?

E1E^{-1} and EE are lower triangular. Its off-diagonal entry is lijl_{ij} the undo the subtraction produced by lij-l_{ij}. The main diagonals contain 1's.

LDU. Lower triangular L times diagonal D times upper triangular U.

A=LDU=L[d1d2...dn][1u12/d1u13/d1...1u23/d2.........1]A=LDU=L\begin{bmatrix} d_1 & & \\ & d_2 & \\ & & .\\ & & & .\\ & & & &.\\ & & & &&d_n\\ \end{bmatrix} \begin{bmatrix} 1 & u_{12}/d_1 & u_{13}/d_1 &.&.&.\\ & 1 & u_{23}/d_{2}&.&.&.\\ & & .&&&.\\ & & & . &&.\\ & & & &.&.\\ & & & & &1\\ \end{bmatrix}

One square system.

System: Ax=b\text{System: } Ax=b
O(n3) Factor: A=LU O(n^3)\text{ Factor: }A=LU \text{ }
O(n2) Solve: Lc=bUx=cO(n^2) \text{ Solve: }Lc=b \text{, } Ux=c
 Gauss elimination with no row exchanges\text{ Gauss elimination with no row exchanges}

A band matrix B has w nonzero diagonals below and above its main diagonal.

Factor: O(n3)O(n^3) to O(nw2)O(nw^2). Solve: O(n2)O(n^2) to O(2nw)O(2nw).

Most matrices in practice are sparce (many zero entries). In that case A=LU is much faster.

n=10310^3. 1 second.

n=10410^4. 10310^3 seconds.

n=10510^5. 10610^6 seconds.

This is too expensive without a supercomputer, but that these matrices are full. Most matrices in practice are sparse (many zero entries). In that case, A=LU is much faster.

Transposes and Permutations

Unprofesional definition (AT)ij=Aji (The columns AT are the rows of A)\text{Unprofesional definition }(A^T)_{ij} = A_{ji} \text{ (The columns } A^T \text{ are the rows of A)}
Profesional definition. (Ax)Ty=xT(ATy)\text{Profesional definition. } (Ax)^Ty = x^T(A^Ty)
Scalar (kA)T=kAT\text{Scalar } (kA)^T=kA^T
Sum (A+B)T=AT+BT\text{Sum } (A+B)^T=A^T+B^T
Product (AB)T=BTAT\text{Product } (AB)^T=B^TA^T

Inverse (A1)T=(AT)1\text{Inverse } (A^{-1})^T=(A^T)^{-1}

The meaning of Inner Products

T is inside. The dot product or inner product is xTy=xy=number=<xy>x^Ty=x·y=number=<x|y> (1xn)(1xn)

T is outside. The rank one product or outer product is xyT=x><y=matrixxy^T=|x><y|=matrix (nx1)(1xn)

Symmetric Matrices

Definition. ST=S\text{Definition. }S^T=S

These are the most important matrices of all.

S=LDU=LDLTS=LDU=LDL^T

Permutation matrices

Definition. A permutation matrix P has the rows of the identity I in any order

Single 1 in every row and every column. There are n! permutation matrices of order n.

And P1=PTP^{-1}=P^T

If A is invertible then a permutation P will reorder its rows for

PA=LUPA=LU

Worked examples

  1. ATA=0A^TA=0 and A0A\ne 0  is impossible.
    diag(ATA)=((col i of A)T(col i of A))ii0 ATA=0diag(ATA)=0((col i of A)T(col i of A))ii=0(col i of A)=0A=0diag(A^TA)=((col\text{ }i\text{ of }A)^T(col\text{ }i\text{ of }A))_{ii}\geq0 \\ \text{ }A^TA=0\\ diag(A^TA)=0\\ ((col\text{ }i\text{ of }A)^T(col\text{ }i\text{ of }A))_{ii}=0\\ (col\text{ }i\text{ of }A)=0\\ A=0
  1. Find P3x33=IP^3_{3x3}=I (but not P = I)

(123),(231),(312),(123)P[123]=[231]P[231]=[312]P[312]=[123]P=[100001010][010100001]=[010001100]Thus, P3=I(123),(231),(312),(123)\\ P\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}=\begin{bmatrix} 2 \\ 3 \\ 1 \end{bmatrix}\\ P\begin{bmatrix} 2 \\ 3 \\ 1 \end{bmatrix}=\begin{bmatrix} 3 \\ 1 \\ 2 \end{bmatrix}\\ P\begin{bmatrix} 3 \\ 1 \\ 2 \end{bmatrix}=\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}\\ P=\begin{bmatrix} 1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 1 & 0 \end{bmatrix}\begin{bmatrix} 0 & 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1 \end{bmatrix}=\begin{bmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{bmatrix}\\ \text{Thus, }P^3=I

3. Find P4x44IP^4_{4x4}\neq I

(1234),(1342),(1423),(1234),(1342)P=[1P3]Thus, P4x44I(1234),(1342),(1423),(1234),(1342)\\ P=\begin{bmatrix} 1 & &&\\ & & P^3&\\ & & & \end{bmatrix}\\ \text{Thus, }P^4_{4x4}\neq I

4. Prove that the identity matrix cannot be te product of three row exchanges (or five). It can be the product of two exchanges (or four).

We have a permutation matrix EpE_p with only two rows distinct to II. It represents a row exchange.

Key properties: Ep=(Ep)T=(Ep)1E_p=(E_p)^T=(E_p)^{-1}, EP2n=I,Ep2n+1=EpE_P^{2n}=I,E_p^{2n+1}=E_p

Vector Spaces

This the highest level of understating about matrix calculations.
DEFINITION. The standard n-dimensional space RnR^n consists of all column vectors vv with nn real components.

The "vectors" in S can be matrices or functions of x.

M (2 by 2 matrices) and F (functions) and Z (zero vector alone) are vector spaces.M \text{ (2 by 2 matrices) and } F \text{ (functions) and } Z \text{ (zero vector alone) are vector spaces.} 

Properties

x+y=y+xx+(y+z)=(x+y)+zx+0=xx+(x)=01×x=x(c1c2)x=c1(c2x)c(x+y)=cx+cy(c1+c2)=c1x+c2xx+y=y+x\\ x+(y+z)=(x+y)+z\\ x+0=x\\ x+(-x)=0\\ 1\times x=x\\ (c_1c_2)x=c_1(c_2x)\\ c(x+y)=cx+cy\\ (c_1+c_2)=c_1x+c_2x

Max-plus vector space

An interesting “max-plus” vector space comes from the real numbers R combined with −∞. Change addition to give x + y = max(x, y) and change multiplication to xy = usual x + y. Which y is the zero vector that gives x+0 = max(x, 0) = x for every x?

Subspace

DEFINITION. A subspace of a vector space is a set of vectors (incluiding 0) that two requirements:

If v and w are vectors in the subspace and c is any scalar, then

v+wv+w is in the subspace.

cvcv is in the subspace.

The smallest subspace

The linear span (also called the linear hull or just span) of a set S of vectors in a vector space is the smallest linear subspace that contains the set.

Column space

C(A) is a combination of r (number of pivots) columns.

Nullspace

N(A) is a combination of n-r special solutions.

Numerical Linear Algebra