🔢

# Linear algebra

Tags Math @May 8, 2020 7:40 PM @August 1, 2021 8:22 AM

# 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].

# Inverse matrices

#### Review of key ideas

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

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

The key reason why A=LU:

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

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

One square system.

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

Factor: $O(n^3)$﻿ to $O(nw^2)$﻿. Solve: $O(n^2)$﻿ to $O(2nw)$﻿.

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

n=$10^3$﻿. 1 second.

n=$10^4$﻿. $10^3$﻿ seconds.

n=$10^5$﻿. $10^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

• Proof

If B is a vector x, such that

If B is $[x_1 x_2 ...]$﻿, such that

• Proof

# The meaning of Inner Products

T is inside. The dot product or inner product is $x^Ty=x·y=number=$﻿ (1xn)(1xn)

T is outside. The rank one product or outer product is $xy^T=|x>﻿ (nx1)(1xn)

# Symmetric Matrices

These are the most important matrices of all.

# 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 $P^{-1}=P^T$﻿

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

## Worked examples

1. $A^TA=0$﻿ and $A\ne 0$﻿ is impossible.
1. Find $P^3_{3x3}=I$﻿ (but not P = I)

3. Find $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 $E_p$﻿ with only two rows distinct to $I$﻿. It represents a row exchange.

Key properties: $E_p=(E_p)^T=(E_p)^{-1}$﻿, $E_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 $R^n$﻿ consists of all column vectors $v$﻿ with $n$﻿ real components.

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

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

## 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+w$﻿ is in the subspace.

$cv$﻿ 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.