Skip to content Skip to navigation Skip to collection information

OpenStax-CNX

You are here: Home » Content » Statistical Signal Processing » Review of Linear Algebra

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

In these lenses

  • SigProc display tagshide tags

    This module is included inLens: Signal Processing
    By: Daniel McKennaAs a part of collection: "Fundamentals of Signal Processing"

    Click the "SigProc" link to see all content selected in this lens.

    Click the tag icon tag icon to display tags associated with this content.

  • Busbee's Math Materials display tagshide tags

    This module is included inLens: Busbee's Math Materials Lens
    By: Kenneth Leroy Busbee

    Click the "Busbee's Math Materials" link to see all content selected in this lens.

    Click the tag icon tag icon to display tags associated with this content.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

Review of Linear Algebra

Module by: Clayton Scott. E-mail the author

Vector spaces are the principal object of study in linear algebra. A vector space is always defined with respect to a field of scalars.

Fields

A field is a set FF equipped with two operations, addition and mulitplication, and containing two special members 0 and 1 ( 01 0 1 ), such that for all abcF a b c F

    1. (a+b)F a b F
    2. a+b=b+a a b b a
    3. ( a + b ) + c = a + ( b + c ) ( a + b ) + c a + ( b + c )
    4. a+0=a a 0 a
    5. there exists a a such that a+a=0 a a 0
    1. abF a b F
    2. ab=ba a b b a
    3. (ab)c=a(bc) a b c a b c
    4. a · 1 =a a · 1 a
    5. there exists a-1 a such that aa-1=1 a a 1
  1. a(b+c)=ab+ac a b c a b a c
More concisely
  1. FF is an abelian group under addition
  2. FF is an abelian group under multiplication
  3. multiplication distributes over addition

Examples

ℚ, ℝ, ℂ

Vector Spaces

Let FF be a field, and VV a set. We say VV is a vector space over F F if there exist two operations, defined for all aF a F , uV u V and vV v V :

  • vector addition: (uu, vv) → (u+v)V u v V
  • scalar multiplication: (aa,vv) → avV a v V
and if there exists an element denoted 0V 0 V , such that the following hold for all aF a F , bF b F , and uV u V , vV v V , and wV w V
    1. u + ( v + w ) = ( u + v ) + w u + ( v + w ) ( u + v ) + w
    2. u+v=v+u u v v u
    3. u+0=u u 0 u
    4. there exists u u such that u+u=0 u u 0
    1. a(u+v)=au+av a u v a u a v
    2. (a+b)u=au+bu a b u a u b u
    3. (ab)u=a(bu) a b u a b u
    4. 1 · u =u 1 · u u
More concisely,
  1. VV is an abelian group under plus
  2. Natural properties of scalar multiplication

Examples

  • RN N is a vector space over ℝ
  • CN N is a vector space over ℂ
  • CN N is a vector space over ℝ
  • RN N is not a vector space over ℂ
The elements of VV are called vectors.

Euclidean Space

Throughout this course we will think of a signal as a vector x= x 1 x 2 x N =( x 1 x 2 x N )T x x 1 x 2 x N x 1 x 2 x N The samples x i x i could be samples from a finite duration, continuous time signal, for example.

A signal will belong to one of two vector spaces:

Real Euclidean space

xRN x N (over ℝ)

Complex Euclidean space

xCN x N (over ℂ)

Subspaces

Let VV be a vector space over FF.

A subset SV S V is called a subspace of VV if SS is a vector space over FF in its own right.

Example 1

V=R2 V 2 , F=R F , S=any line though the origin S any line though the origin .

Figure 1: SS is any line through the origin.
Figure 1 (subspace.png)

Are there other subspaces?

Theorem 1

SV S V is a subspace if and only if for all aF a F and bF b F and for all sS s S and tS t S , (as+bt)S a s b t S

Linear Independence

Let u 1 , , u k V u 1 , , u k V .

We say that these vectors are linearly dependent if there exist scalars a 1 , , a k F a 1 , , a k F such that

i =1k a i u i =0 i 1 k a i u i 0
(1)
and at least one a i 0 a i 0 .

If Equation 1 only holds for the case a 1 == a k =0 a 1 a k 0 , we say that the vectors are linearly independent.

Example 2

11-122-230+1-57-2=0 1 1 -1 2 2 -2 3 0 1 -5 7 -2 0 so these vectors are linearly dependent in R3 3 .

Spanning Sets

Consider the subset S= v 1 v 2 v k S v 1 v 2 v k . Define the span of SS < S > spanS i =1k a i v i a i F < S > span S i 1 k a i v i a i F

Fact: < S > < S > is a subspace of VV.

Example 3

V=R3 V 3 , F=R F , S= v 1 v 2 S v 1 v 2 , v 1 =100 v 1 1 0 0 , v 2 =010 v 2 0 1 0 < S > =xy-plane < S > xy-plane .

Figure 2: < S > < S > is the xy-plane.
Figure 2 (span.png)

Aside

If SS is infinite, the notions of linear independence and span are easily generalized:

We say SS is linearly independent if, for every finite collection u 1 , , u k S u 1 , , u k S , (kk arbitrary) we have ( i =1k a i u i =0) a i =0   i 1 k a i u i 0 i a i 0 The span of SS is < S > = i =1k a i u i a i F u i S(k<) < S > i 1 k a i u i a i F u i S k

Note:

In both definitions, we only consider finite sums.

Bases

A set BV B V is called a basis for VV over FF if and only if

  1. B B is linearly independent
  2. < B > =V < B > V
Bases are of fundamental importance in signal processing. They allow us to decompose a signal into building blocks (basis vectors) that are often more easily understood.

Example 4

VV = (real or complex) Euclidean space, RN N or CN N . B= e 1 e N standard basis B e 1 e N standard basis e i =010 e i 0 1 0 where the 1 is in the ith i th position.

Example 5

V=CN V N over ℂ. B= u 1 u N B u 1 u N which is the DFT basis. u k =1e(i2πkN)e(i2πkN(N1)) u k 1 2 k N 2 k N N 1 where i=-1 -1 .

Key Fact

If BB is a basis for VV, then every vV v V can be written uniquely (up to order of terms) in the form v= i =1N a i v i v i 1 N a i v i where a i F a i F and v i B v i B .

Other Facts

  • If SS is a linearly independent set, then SS can be extended to a basis.
  • If < S > =V < S > V , then SS contains a basis.

Dimension

Let VV be a vector space with basis BB. The dimension of VV, denoted dimV dim V , is the cardinality of BB.

Theorem 2

Every vector space has a basis.

Theorem 3

Every basis for a vector space has the same cardinality.

dimV dim V is well-defined.

If dimV< dim V , we say VV is finite dimensional.

Examples

Table 1
vector space field of scalars dimension
RN N R
CN N C
CN N R

Every subspace is a vector space, and therefore has its own dimension.

Example 6

Suppose (S= u 1 u k )V S u 1 u k V is a linearly independent set. Then dim < S > = dim < S >

Facts

  • If SS is a subspace of VV, then dimSdimV dim S dim V .
  • If dimS=dimV< dim S dim V , then S=V S V .

Direct Sums

Let VV be a vector space, and let SV S V and TV T V be subspaces.

We say VV is the direct sum of SS and TT, written V=ST V S T , if and only if for every vV v V , there exist unique sS s S and tT t T such that v=s+t v s t .

If V=ST V S T , then TT is called a complement of SS.

Example 7

V= C = { f : R R | f is continuous } V C { f : | f is continuous } S= even funcitons in C S even funcitons in C T= odd funcitons in C T odd funcitons in C ft=12(ft+ft)+12(ftft) f t 1 2 f t f t 1 2 f t f t If f=g+h= g + h f g h g h , gS g S and g S g S , hT h T and h T h T , then g g = h h g g h h is odd and even, which implies g= g g g and h= h h h .

Facts

  1. Every subspace has a complement
  2. V=ST V S T if and only if
    1. ST=0 S T 0
    2. < S , T > =V < S , T > V
  3. If V=ST V S T , and dimV< dim V , then dimV=dimS+dimT dim V dim S dim T

Proofs

Invoke a basis.

Norms

Let VV be a vector space over FF. A norm is a mapping VF V F , denoted by · · , such that forall uV u V , vV v V , and λF λ F

  1. u>0 u 0 if u0 u 0
  2. λu=|λ|u λ u λ u
  3. u+vu+v u v u v

Examples

Euclidean norms:

xRN x N : x= i =1N x i 212 x i 1 N x i 2 1 2 xCN x N : x= i =1N| x i |212 x i 1 N x i 2 1 2

Induced Metric

Every norm induces a metric on VV duvuv d u v u v which leads to a notion of "distance" between vectors.

Inner products

Let V V be a vector space over FF, F=R F or C. An inner product is a mapping V×V F V V F , denoted ·,· · · , such that

  1. v,v0 v v 0 , and v,v=0v=0 v v 0 v 0
  2. u,v=v,u¯ u v v u
  3. au+bv,w=a(u,w)+b(v,w) a u b v w a u w b v w

Examples

RN N over ℝ: x,y=(xTy)= i =1N x i y i x y x y i 1 N x i y i

CN N over ℂ: x,y=(xHy)= i =1N x i ¯ y i x y x y i 1 N x i y i

If (x= x 1 x N T)C x x 1 x N , then xH x 1 ¯ x N ¯T x x 1 x N is called the "Hermitian," or "conjugate transpose" of xx.

Triangle Inequality

If we define u=u,u u u u , then u+vu+v u v u v Hence, every inner product induces a norm.

Cauchy-Schwarz Inequality

For all uV u V , vV v V , |u,v|uv u v u v In inner product spaces, we have a notion of the angle between two vectors: (uv=arccosu,vuv) 0 2π u v u v u v 0 2

Orthogonality

uu and vv are orthogonal if u,v=0 u v 0 Notation: uv u v .

If in addition u=v=1 u v 1 , we say uu and vv are orthonormal.

In an orthogonal (orthonormal) set, each pair of vectors is orthogonal (orthonormal).

Figure 3: Orthogonal vectors in R2 2 .
Figure 3 (orthogonal.png)

Orthonormal Bases

An Orthonormal basis is a basis v i v i such that v i , v i = δ i j ={1  if  i=j0  if  ij v i v i δ i j 1 i j 0 i j

Example 8

The standard basis for RN N or CN N

Example 9

The normalized DFT basis u k =1N1e(i2πkN)e(i2πkN(N1)) u k 1 N 1 2 k N 2 k N N 1

Expansion Coefficients

If the representation of vv with respect to v i v i is v= i a i v i v i a i v i then a i = v i ,v a i v i v

Gram-Schmidt

Every inner product space has an orthonormal basis. Any (countable) basis can be made orthogonal by the Gram-Schmidt orthogonalization process.

Orthogonal Compliments

Let SV S V be a subspace. The orthogonal compliment SS is S = u uV(u,v=0)vS   S u u V u v 0 v v S S S is easily seen to be a subspace.

If dimv< dim v , then V=S S V S S .

Aside:

If dimv= dim v , then in order to have V=S S V S S we require VV to be a Hilbert Space.

Linear Transformations

Loosely speaking, a linear transformation is a mapping from one vector space to another that preserves vector space operations.

More precisely, let VV, WW be vector spaces over the same field FF. A linear transformation is a mapping T : V W T : V W such that Tau+bv=aTu+bTv T a u b v a T u b T v for all aF a F , bF b F and uV u V , vV v V .

In this class we will be concerned with linear transformations between (real or complex) Euclidean spaces, or subspaces thereof.

Image

imageT= w wW Tv=w for some v T w w W T v w for some v

Nullspace

Also known as the kernel: kerT= v vV(Tv=0) ker T v v V T v 0

Both the image and the nullspace are easily seen to be subspaces.

Rank

rankT=dimimageT rank T dim T

Nullity

nullT=dimkerT null T dim ker T

Rank plus nullity theorem

rankT+nullT=dimV rank T null T dim V

Matrices

Every linear transformation TT has a matrix representation. If T : 𝔼 N 𝔼 M T : 𝔼 N 𝔼 M , 𝔼=R 𝔼 or C, then TT is represented by an M×N M N matrix A=( a 1 1 a 1 N a M 1 a M N ) A a 1 1 a 1 N a M 1 a M N where a 1 i a M i T=T e i a 1 i a M i T e i and e i =010T e i 0 1 0 is the ith i th standard basis vector.

Aside:

A linear transformation can be represented with respect to any bases of 𝔼N 𝔼 N and 𝔼M 𝔼 M , leading to a different AA. We will always represent a linear transformation using the standard bases.

Column span

colspanA= < A > =imageA colspan A < A > A

Duality

If A : R N R M A : N M , then kerA=imageAT ker A A

Figure 4
Figure 4 (dual.png)

If A : C N C M A : N M , then kerA=imageAH ker A A

Inverses

The linear transformation/matrix AA is invertible if and only if there exists a matrix BB such that AB=BA=I A B B A I (identity).

Only square matrices can be invertible.

Theorem 4

Let A : 𝔽 N 𝔽 N A : 𝔽 N 𝔽 N be linear, 𝔽=R 𝔽 or C. The following are equivalent:

  1. AA is invertible (nonsingular)
  2. rankA=N rank A N
  3. nullA=0 null A 0
  4. detA0 A 0
  5. The columns of AA form a basis.

If A-1=AT A A (or AH A in the complex case), we say AA is orthogonal (or unitary).

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks