A Summary of Linear Algebra

vs 0.5, 25/1/08 © Niels Walet

In this document I will summarise some key results of Linear Algebra, as is useful for background in the course.

. Vectors and matrices

You have all seen the rather labourious notation v=(Subscript[v, 1])i+(Subscript[v, 2]) j+(Subscript[v, 3]) k. Instead we prefer to use the row- and, more usually, column vector notation
v=((Subscript[v, 1]),(Subscript[v, 2]),(Subscript[v, 3])) or v=(({{(Subscript[v, 1])
(Subscript[v, 2])}, {(Subscript[v, 3])}})).
This is easily generalised to vectors of different dimension (number of entries).
Vectors are special case of a matrix, which is an object with multiple rows and columns, e.g., 
M=(({{1, 2}, {3, 4}})),
is called a two-by two matrix. When finding entries of matrices, we use the notation (Subscript[M, i j]) for the entry in the ith row and the jth column.

Mathematica Notation

Within Mathematica  a matrix is define as a "double list", a list of row vectors

M={{a,b},{c,d}}

We usually get entries of the matrix by typing (Subscript[M, i j]) for the element in the ith row and jth column. In Mathematica entries are found using the notation [[i]][[j]]:

M[[2]][[1]]

Question: define a column vector (({{1}, {2}})) in Mathematica.

The inner product is denoted by a dot,

{1,2}.{2,3}

{1,2}.(({{2}, {3}}))

Note the extra brackets in the last expression, to be explained below.

Products of Matrices

We calculate matrix product according to the row × column recipe, where we take the "inner-product" of the ith row of the object on the left, with the jth column of the object on the right, to generate the i ,j entry for the result.
(Subscript[M, i j])=(∑_(k=1)^m)(Subscript[N, i k])(Subscript[O, k j])

Example: Multiply (({{1, 3}, {4, 5}})) by (({{-1, 3}, {-4, 5}})).
We first multiply the first row of the left matrix with the first column of the right, (1,3).(-1,-4)=-13. Then the second row times the first column (to get the entry of the result in first column and second row), (4,5).(-1,-4)=-24. First row and second column gives (1,3).(3,5)=18, and finally second row and second column (4,5).(3,5)=37. Thus (({{1, 3}, {4, 5}}))(({{-1, 3}, {-4, 5}}))=(({{-13, 18}, {-24, 37}})).  In Mathematica (Notice the use of the dot between the matrices to denote the product!):

(({{1, 3}, {4, 5}})).(({{-1, 3}, {-4, 5}}))

Exercise

(({{1, 2}, {3, 4}, {5, 6}})).(({{5, -3}, {1, 2}}))

Exercise

Inverse

The inverse (M^(-1)) of a matrix M is defined by the relation (M^(-1)) M=M (M^(-1))=I, where I is the appropriate identity matrix (a matrix that is zero apart from on the main diagonal, where it has ones). E.g., execute the following Mathematica code

M=(({{1, 2, 3}, {4, 5, 6}, {7, 8, 10}}))

Minv=Inverse [M]

Minv . M

Note that an invertible matrix (with an existing inverse) is always "square" with equal column and row dimension. A good technique to calculate the inverse is the elimination method, which is discussed in the section "Simultaneous equations"

Determinants

The determinant of a square matrix is given by an expansion ("the Laplacian development by minors"). First we assign each entry a sign (+ or -) starting with a +  in the top left corner of the matrix, making sure that each direct neighbour, in row or column, has the opposite sign, i.e., of the following form

(({{+, -, +, -}, {-, +, -, +}, {+, -, +, -}, {-, +, -, +}})).

We then pick one row or a column, take each element of the row or column in turn, multiply it by its sign and by the determinant with all elements in the row and column of the current element removed, until we end up with a 1×1 matrix. Let's look at that, expanding the following matrix by the second column

|({{1, 2, 3, 4}, {5, 4, 1, 2}, {6, 8, 0, 3}, {4, 7, 2, 1}})|=-2|({{5, 1, 2}, {6, 0, 3}, {4, 2, 1}})|+4|({{1, 3, 4}, {6, 0, 3}, {4, 2, 1}})|-8|({{1, 3, 4}, {5, 1, 2}, {4, 2, 1}})|+7|({{1, 3, 4}, {5, 1, 2}, {6, 0, 3}})|.

Now expand all of the determinants w.r.t. to the middle column,

|({{1, 2, 3, 4}, {5, 4, 1, 2}, {6, 8, 0, 3}, {4, 7, 2, 1}})|=-2(-1|({{6, 3}, {4, 1}})|-2|({{5, 2}, {6, 3}})|)+4(-3|({{6, 3}, {4, 1}})|-2|({{1, 4}, {6, 3}})|)-8(-3|({{5, 2}, {4, 1}})|+1|({{1, 4}, {4, 1}})|-2|({{1, 4}, {5, 2}})|)+7(-3|({{5, 2}, {6, 3}})|+1|({{1, 4}, {6, 3}})|)=-2(-1(-6)-2(3))+4(-3(-6)-2(-21))-8(-3(-3)+1(-15)-2(-18))+7(-3(3)+1(-21))=-210

Check using Mathematica

Det[(({{1, 2, 3, 4}, {5, 4, 1, 2}, {6, 8, 0, 3}, {4, 7, 2, 1}}))]

Another example

M=(({{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}))

Det[M]

Inverse[M]

So if a determinant is zero, an inverse doesn't exist!

A useful property of a determinant is that det(A B)=det(A) det(B), det((A^(-1)))=1/det(A).These can be used to show that the determinant is the product of eigenvalues (see below).
Also, more importantly a determinant is antisymmetric under the interchange of any rows or column, i.e., it changes its sign. This can be used to show we can add any column (or row) to another matrix without changing the determinant,

det(({{(Subscript[a, 1])+k (Subscript[a, 3]), (Subscript[a, 2]), (Subscript[a, 3])}, {(Subscript[b, 1])+k (Subscript[b, 3]), (Subscript[b, 2]), (Subscript[b, 3])}, {(Subscript[c, 1])+k (Subscript[c, 3]), (Subscript[c, 2]), (Subscript[c, 3])}}))=det(({{(Subscript[a, 1]), (Subscript[a, 2]), (Subscript[a, 3])}, {(Subscript[b, 1]), (Subscript[b, 2]), (Subscript[b, 3])}, {(Subscript[c, 1]), (Subscript[c, 2]), (Subscript[c, 3])}}))+k det(({{(Subscript[a, 3]), (Subscript[a, 2]), (Subscript[a, 3])}, {(Subscript[b, 3]), (Subscript[b, 2]), (Subscript[b, 3])}, {(Subscript[c, 3]), (Subscript[c, 2]), (Subscript[c, 3])}}))=det(({{(Subscript[a, 1]), (Subscript[a, 2]), (Subscript[a, 3])}, {(Subscript[b, 1]), (Subscript[b, 2]), (Subscript[b, 3])}, {(Subscript[c, 1]), (Subscript[c, 2]), (Subscript[c, 3])}})).

Here we equated the second determinant to zero, since it must change sign under interchange of two identical columns, an impossibility unless the answer is zero.

Trace

The trace of a matrix is the sum of all the diagonal elements (the ones with equal row- and column index):

Tr(H)=(∑_(i=1)^n)(Subscript[H, i i]).

This can be shown to equal the sum of eigenvalues (see below). Equally useful is the cyclicity of the trace,

Tr(A B C)=Tr(C A B)=Tr(B C A).

The proof is rather simple for two matrices,

Tr(A D)=(∑_(i ))(Subscript[(A D), i i])=(∑_(i j))(Subscript[A, i j])(Subscript[D, j i ])=(∑_j)(Subscript[(D A), j j])=Tr(D A).

Using D=B C we get the desired expression.

Symmetric and Hermitian Matrices

A very common operation on matrices is transposition (denoted by "T"), where we swap rows and columns, or mirror in the main diagonal,  (Subscript[((M^T)), i j])≡(Subscript[M, j i]). It is straightforward to show that (((A B))^T)=(B^T)(A^T),

(Subscript[((((A B))^T)), i j])=(∑_k)(Subscript[A, j k])(Subscript[B, k i])=(∑_k)(Subscript[((B^T)), i k])(Subscript[((A^T)), k j])=(Subscript[((B^T)(A^T)), i j]).

Symmetric matrices don't change under transposition. We usually reserve the term symmetric for real matrices:
Thus (Subscript[((M^T)), i j])≡(Subscript[M, j i]), and for a symmetric matrix (Subscript[M, i j ])=(Subscript[M, j i]).
For complex matrices we normally combine the action of transposition with complex conjugation to obtain the Hermitian conjugate of a matrix, (SuperDagger[M])≡(SuperStar[((M^T))]), and in index notation (Subscript[((SuperDagger[M])), i j])≡(SuperStar[((Subscript[M, j i]))]). For a Hermitian matrix (SuperDagger[M])=M, or (Subscript[M, i j ])=(SuperStar[((Subscript[M, j i ]))]).

See Eric W.Weisstein."Hermitian Matrix." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/HermitianMatrix.html

Pauli matrices

A very useful set of Hermitian matrices are the three Pauli (spin) matrices

(Subscript[σ, x])=(({{0, 1}, {1, 0}}));(Subscript[σ, y])=(({{0, -I}, {I, 0}})) ;(Subscript[σ, z])=(({{1, 0}, {0, -1}})) ;

If we multiply two of these matrices we always obtain i times the 3rd:

(Subscript[σ, x]).(Subscript[σ, y])
(Subscript[σ, y]).(Subscript[σ, z])
(Subscript[σ, z]).(Subscript[σ, x])

A 4×4 example

The matrix (({{2, 3+i, 4+2 i, 5+3 i}, {3-i, 4, 5+i, 6+2 i}, {4-2 i, 5-i, 6, 7+i}, {5-3 i, 6-2 i, 7-i, 8}})) is Hermitian. Note that the entries on the diagonal are always real!

Exercise

M=(({{1, 1+I, 3}, {3, I, 4}, {5, 2 I, 7}, {9, I, 2+3 I}}))

ConjugateTranspose[M]

. Simultaneous equations

The equation
{({{x+y=5}, {x-y=2}}) 
can be written in matrix language as
(({{1, 1}, {1, -1}}))(({{x}, {y}}))=(({{5}, {2}})).
This has as solution
(({{x}, {y}}))=(((({{1, 1}, {1, -1}})))^(-1))(({{5}, {2}})).
From

(({{1, 1}, {1, -1}})).(({{1, 1}, {1, -1}}))

We conclude that (((({{1, 1}, {1, -1}})))^(-1))=(({{1/2, 1/2}, {1/2, -1/2}})), and thus (({{x}, {y}}))=(({{7/2}, {3/2}})).

Solve[{x+y==5,x-y==2}]

Elimination and calculation of the inverse

One easy technique for inverting a matrix is the "Gaussian elimination technique", where we start with a matrix (in this case (({{1, 2, 3}, {4, 5, 6}, {7, 8, 10}}))), and extend it with the identity matrix as shown below:

sys=(({{1, 2, 3, 1, 0, 0}, {4, 5, 6, 0, 1, 0}, {7, 8, 10, 0, 0, 1}}));

By elimination (adding and subtracting rows) we try to have the identity appear in the first half, and generate the inverse in the second half (sys[[i]] gives the ith row)

sys={sys[[1]]-1/2sys[[2]],sys[[2]]-sys[[3]]+3 sys[[1]],sys[[3]]-4 sys[[1]]}

{4(sys[[1]]+sys[[2]]/6+sys[[3]] 5 /12),-4/3(sys[[2]]+5/2sys[[3]]+15/2sys[[1]]),2 (sys[[3]]+3sys[[1]]+1/2sys[[2]])}

So let's check we have indeed found the inverse:

(({{1, 2, 3}, {4, 5, 6}, {7, 8, 10}})).(({{-(2/3), -(4/3), 1}, {-(2/3), (11/3), -2}, {1, -2, 1}}))

The reason this works is actually quite simple. If we multiply the extended matrix by the column vector (((x,y,z,a,b,c))^T) we can clearly see that
(({{1, 2, 3, 1, 0, 0}, {4, 5, 6, 0, 1, 0}, {7, 8, 10, 0, 0, 1}}))(({{x}, {y}, {z}, {a}, {b}, {c}}))=(({{1, 2, 3}, {4, 5, 6}, {7, 8, 10}}))(({{x}, {y}, {z}}))+(({{a}, {b}, {c}})). If we assume this has right-hand side zero, we are solving the most general set of equations for fixed coefficients. After all the manipulations the right-hand side remains zero, but the equation now reads 
(({{-(2/3), -(4/3), 1}, {-(2/3), (11/3), -2}, {1, -2, 1}}))(({{a}, {b}, {c}}))+(({{x}, {y}, {z}}))=(({{0}, {0}, {0}})), which means we have found the inverse.

Exercise

Inverse[(({{0, -2, 1}, {2, 4, 0}, {1, 1, 2}}))]

Determinants, existence and non-uniqueness

As stated above determinants don't change if we add a column to another column, or a row to another row. Thus the invertability of a matrix (uniqueness of its solution) is also not influenced by this. But if a determinant is zero, we now that we may be able to express one column as a linear combination of the others (a rather deep corollary of the antisymmetry property). Thus we conclude that a zero determinant means a dependent set of equations, and an underdetermined solution. In other words this corresponds to a non-invertible matrix.

. Eigenvalues and eigenvectors

Eigenproblems

An eigenvalue problem is one where a n×n matrix reproduces a vector,

(∑_j)(Subscript[M, i j]) (Subscript[e, j])=λ (Subscript[e, i]).

With the help of the identity matrix, I=diag(1,1,1,...,1), e.g.,

IdentityMatrix[5]

We can turn this into a homogeneous set of equations

(M-λ I) e=0.

We are now interested in the case that there is more than a zero solution. This means e is not unique! Also we can use the fact that non-uniqueness requires (M-λ I) not to have an inverse, or det(M-λ I)=0 . This is an nth order polynomial equation for the eigenvalues λ, with in general n complex roots. Thus we have n eigenvalues and eigenvectors. Strictly speaking the eigenvectors defined above are the right eigenvectors, which are different from the left eigenvector, which occur for the same eigenvalue, but multiply M from the left,

(∑_i)(Subscript[l, i]) (Subscript[M, i j])=λ (Subscript[l, j])

The matrix of eigenvectors

We rewrite the eigenvalue problem by labelling the eigenvalues and (right) eigenvectors (λ^((j))), (Subscript[e, i]^((j)))  for i,j=1,...,n,

(∑_j)(Subscript[M, i j]) (Subscript[e, j]^((k)))=(λ^((k))) (Subscript[e, i]^((k))),

and then define the matrix of eigenvectors (Subscript[O, j k])=(Subscript[e, j]^((k))). We get

(∑_j)(Subscript[M, i j]) (Subscript[O, j k])=(Subscript[O, i k])(λ^((k))) .

If we know the inverse (O^(-1)) of O,

(∑_j)(Subscript[((O^(-1))), i j]) (Subscript[O, j k])=(Subscript[δ, i j])

(where (Subscript[δ, i j]) is another way to denote the n×n unit matrix), we can left multiply the eigenvalue problem by (O^(-1)) to get

(∑_(i j))(Subscript[((O^(-1))), l i])(Subscript[M, i j])(Subscript[O, j k])=(λ^((k)))(Subscript[δ, l k])

which can be cast in the slightly more compact form

(O^(-1))M O=diag((Subscript[λ, 1]),....,(Subscript[λ, n])).

We have now "diagonalised" the matrix M. Also note that (O^(-1)) is the matrix of left eigenvectors with a suitable normalisation,

(Subscript[((O^(-1))), i j])=(Subscript[l, i]^((j))), (l^((j))). (e^((k)))=(Subscript[δ, j k]).

Exercise

t=Eigensystem[(({{0, -2, 1}, {2, 4, 0}, {1, 1, 2}}))];eval=t[[1]];evec=Transpose[t[[2]]]
Inverse[evec ]. (({{0, -2, 1}, {2, 4, 0}, {1, 1, 2}})) . evec

Special cases: Symmetric and Hermitian matrices; Orthogonal and Unitary matrices

Two very interesting cases of the diagonalisation problem can be found when

1. The matrix M is symmetric. In that case (M^T)=M, and we can rewrite the eigenvalue problem in the form
(O^(-1))M O=diag((Subscript[λ, 1]),....,(Subscript[λ, n]))=(O^T)(M^T) ((((O^(-1))))^T)=(O^T)M ((((O^T)))^(-1)).
(We use ((((O^(-1))))^T)=((((O^T)))^(-1)) in the last expression. Prove for yourself this is true!)
We conclude that we should have (O^T)=(O^(-1)) , or in other words the left and right eigenvalues coincide! The normalisation condition becomes (e^((k))).(e^((l)))=(Subscript[δ, k l]), which is the requirement of "normalised" eigenvectors.
A matrix with the property (O^(-1))=(O^T) is called orthogonal—no big surprise since it is made up of a set of orthonormal vectors (orthogonal vectors with length 1)

Exercise

<<Geometry`Rotations`
Orth=RotationMatrix3D[ϕ,θ, ψ]

Is orthogonal. Check by using Mathematica

TrigExpand[Orth. Transpose[Orth]]

2. The matrix M is Hermitian. In that case (SuperDagger[M])=M, and we can rewrite the eigenvalue problem in the form (checking that the eigenvalues are real!!!)
(O^(-1))M O=diag((Subscript[λ, 1]),....,(Subscript[λ, n]))=(SuperDagger[O])(SuperDagger[M]) (SuperDagger[((O^(-1)))])=(SuperDagger[O])M ((((SuperDagger[O])))^(-1)).
(We use (SuperDagger[((O^(-1)))])=((((SuperDagger[O])))^(-1)) in the last expression. Prove for yourself this is true!)
We conclude that we should have (O^(† ))=(O^(-1)) , or in other words the left and right eigenvalues coincide up to complex conjugation! The normalisation condition becomes (e^(SuperStar[(k)])).(e^((l)))=(Subscript[δ, k l]), which is the requirement of "normalised" eigenvectors in a space of complex vectors.
A matrix with the property (O^(-1))=(SuperDagger[O]) is called unitary, which is why one often writes "U" for such a matrix rather than O.

Exercise

(Subscript[σ, x])=(({{0, 1}, {1, 0}}));(Subscript[σ, y])=(({{0, -I}, {I, 0}})) ;(Subscript[σ, z])=(({{1, 0}, {0, -1}})) ;unitary=Simplify[(Subscript[a, 0]) IdentityMatrix[2]+I ((Subscript[a, 1])  (Subscript[σ, x])+(Subscript[a, 2])  (Subscript[σ, y])+(Subscript[a, 3])  (Subscript[σ, z]))]

is unitary if (∑_i)((Subscript[a, i])^2)=1 and (Subscript[a, i]) is real. Check using Mathematica

ComplexExpand[unitary.ConjugateTranspose[unitary]]