Matrix Decomposition: Inner Products and Norms

MODULE − IV

MATRIX DECOMPOSITION

INNER PRODUCTS AND NORMS

Let us refresh the basic concepts of inner products and norms.

Definition

Let F denote either field of real numbers or complex numbers. Let V be a vector space over F. An inner product on V is a function denoted by

 <•, •> = V×V → F such that

(i) <x, x> ≥ 0 for all x ∈ V

(ii) <x, x> = 0 if and only if x=0

(iii) <α x, y> =α <x, y> for all α ∈ F, x, y ∈ V

(iv) <x, y> = <> for all x, y ∈ V

(v) <x + y, z> = <x, z> + <y, z> for all x, y, z ∈ V

(vi) <0,y> = 0 for all y ∈ V.

Definition

A vector norm is a measure of the length or magnitude of a vector. A norm or length of a vector x in a vector space V denoted by || x || ≥ 0 is a real valued function such that

(i) ||x|| = 0 if and only if x=0

(ii) ||x||≥0 for x ∈ V.

(iii) || αx || = |α| || x || for x ∈ V and α ∈ F

(iv) || x + y || = || x || + || y || (Triangle inequality)

Here we give some examples of norms on Rⁿ.

(i) The inner product generated norm: ||x||_w = √<x, x >_w

(ii) ||x||₂ = √<x, x> (Euclidean or l₂ − norm)

(iii) || x ||₁ = |x₁| + |x₂| + |x₃| + ... + | x_n|       (l₁. − norm)

(iv) || x ||_∞ = Max {|x₁|, |x₂|, |x₃| ... | x_n|^p }^1/P      (l_∞. − norm)

(v) || x ||_P = { |x₁|^p + |x₂|^p + |x₃|^p + ... + | x_n|^p }^1/P      (l_P. − norm)     (p ≥1)

Definition

A unit vector is a vector with norm equal to one.

If x≠0, then y = x / || x || is such that || y || = 1.

Thus every non−zero vector gives a unit vector.

Definition

Each norm on a vector induces or generates a norm on a matrix A by

 || A || = Max || Ax ||

 || x || = 1

Below we give some induced norms.

Let A = [a_ij] be an n×n matrix.

(i) The L₁ norm (induced by the l₁ − norm)

 which is the largest column sum of absolute values.

(ii) The L_∞ norm (induced by the l_∞ - norm)

 which is the largest row sum of absolute values.

(iii) The Frobenius (or) Euclidean norm.

(iv) The spectral norm (induced by the Euclidean norm)

 ||A||_S = Max (√λ; λ is an eigenvalue of A^TA).

Definition: Orthogonality

The vectors are orthogonal if their inner product is zero. Orthogonality reduces to the geometric concept of perpendicularity under the Euclidean inner product when the vectors are real and restricted to two or three dimensions.

A set of vectors is orthogonal if each vector in the set is orthogonal to every other vector in that set. Such a set is linearly independent when the vectors are all non−zero.

Normalized vectors and distance:

A unit vector is a vector having norm equal to unit. A non−zero vector is normalized when it is multiplied by the reciprocal of its norm. Consequently, normalized vectors are unit vectors.

A set of vectors is orthonormal if the set is orthogonal and if each other vector in the set is a unit vector. The distance between two vectors x and y is ||x−y||.

Compatibility

A vector norm is compatible with a matrix norm if || AY || ≤ || A || || Y || for every n×n matrix A and every n−dimensional vector Y. Induced norms are always compatible with the vector norms that generated them and these always exists atleast one vector Y is an equality. Compatibility is not restricted to induced norms and Frobenius norms.

Spectral radius

The spectral radius of a square matrix A denoted by σ (A), is the largest absolute value of any eigenvalue of A.

(ie) σ(A) = Max { | λ |; λ is an eigenvalue of A }

If λ is any eigenvalue of a matrix A, then |λ| ≤ σ(A) and there is atleast one eigenvalue for which this inequality is an equality. For any matrix norm

 σ(A) ≤ ||A||

This provides bounds on the eigenvalues of a matrix.

An equivalent expression for the spectral radius is

      σ(A) = lim_m→∞ ||A^m||^1/m.