[PDF] Notes on vectors and matrices

173885_6notes1.pdf

Notes on vectors and matrices

?

EE103 Winter Quarter 2001-02

L. Vandenberghe

1 Terminology and notation

Matrices, vectors, and scalars

Amatrixis a rectangular array of numbers (also calledscalars), written between brackets, as in A= ? ? ?

01-2.30.1

1.34-0.10

4.1-101.7?

? ? . An important attribute of a matrix is itssizeordimensions,i.e.,thenumbersofrowsand columns. The matrixAabove, for example, has 3 rows and 4 columns, so its size is 3×4. (Size is always given as rows×columns.) Theentriesorcoefficientsorelementsof a matrix are the values in the array. Thei,j entry is the value in theith row andjth column, denoted by double subscripts: thei,jentry ofamatrixCis denotedCij (which is a number). The positive integersiandjare called the (row and column, respectively)indices. For our example above,A13 =-2.3,A 32
=-1. The row index of the bottom left entry (which has value 4.1)is 3; its column index is 1. A matrix with only one column,i.e., with sizen×1, is called acolumn vectoror just a vector. Sometimes the size is specified by calling it ann-vector. The entries of a vector are denoted with just one subscript (since the other is 1), as ina3 . The entries are sometimes called thecomponentsof the vector. As an example, v= ? ? ? ? ?1 -2 3.3 0.3 ? ? ? ?? is a 4-vector (or 4×1 matrix); its third component isv 3 =3.3. We sometimes write a vector by listing its components between parentheses and separated by commas, as in v=(1,-2,3.3,0.3). It is important to keep in mind that this denotes the same column vector as defined above.? BasedontheMatrix Primerby S. Boyd (Stanford University). 1 A matrix with only one row,i.e., with size 1×n, is sometimes called arow vector.As an example, w= ? -2.1-30 ? is a row vector (or 1×3 matrix); its third component isw 3 = 0. Sometimes a 1×1 matrix is considered to be the same as a scalar,i.e.,anumber. Two matrices areequalif they are the same size and all the corresponding entries (which are numbers)are equal.

The set of allm×nmatrices is denotedR

m×n , and the set of alln-vectors is denoted R n . In other words,A?R m×n means the same as 'Ais a matrix with sizem×n," and x?R n means 'xis ann-vector."

Notational conventions

Some authors try to use notation that helps the reader distinguish between matrices, vectors, and scalars (numbers). For example, Greek letters (α,β, ...)mightbeusedfornumbers, lower-case letters (a,x,f, ...)for vectors, and capital letters (A,F, ...)for matrices. Other notational conventions include matrices given in bold font (G), or vectors written with arrows above them (?a). Unfortunately, there are about as many notational conventions as authors, so you should be prepared to figure out what things are (i.e., scalars, vectors, matrices)despite the author"s notational scheme (if any exists).

Zero and identity matrices

The zero matrix (of sizem×n)is the matrix with all entries equal to zero. Sometimes the zero matrix is written as 0 m×n , where the subscript denotes the size. But often, a zero matrix is denoted just 0, the same symbol used to denote the number 0. In this case you"ll have to figure out the size of the zero matrix from the context. (More on this later.) Note that zero matrices of different sizes are different matrices, even though we use the same symbol to denote them (i.e., 0). In programming we call thisoverloading:wesaythe symbol 0 is overloaded because it can mean different things depending on its context (i.e., the equation it appears in). When a zero matrix is a (row or column)vector, we call it a zero (row or column)vector. An identity matrix is another common matrix. It is alwayssquare,i.e., has the same number of rows as columns. Itsdiagonalentries,i.e., those with equal row and column index, are all equal to one, and its off-diagonal entries (those with unequal row and column indices) are zero. Identity matrices are denoted by the letterI. Sometimes a subscript denotes the size, as inI 4 orI

2×2

. But more often the size must be determined from context (just like zero matrices). Formally, the identity matrix of sizenis defined by I ij = ? 1i=j 0i?=j 2

Perhaps more illuminating are the examples

? 10 01 ? , ? ? ? ?? 1000
0100
0010 0001 ? ? ? ?? which are the 2×2and4×4 identity matrices. (Remember that both are denoted with the same symbol -I.) The importance of the identity matrix will become clear later.

2 Matrix operations

Matrices can be combined in various operations to form other matrices.

Matrix transpose

IfAis anm×nmatrix, itstranspose, denotedA

T (or sometimesA ? ),isthen×mmatrix given by ? A T ? ij =A ji . In words, the rows and columns ofAare transposed inA T .For example, ? ? ? 04 70
31
? ? ? T = ? 073
401
? . If we transpose a matrix twice, we get back the original matrix: ? A T ? T =A.

Matrix addition

Two matricesof the same sizecan be added together, to form another matrix (of the same size), by adding the corresponding entries (which are numbers). Matrix addition is denoted by the symbol +. (Thus the symbol + is overloaded to mean scalar addition when scalars appear on its left and right hand side, and matrix addition when matrices appear on its left and right hand sides.)For example, ? ? ? 04 70
31
? ? ? + ? ? ? 12 23
04 ? ? ? = ? ? ? 16 93
35
? ? ? Note that (row or column)vectors of the same size can be added, but you cannot add together a row vector and a column vector (except if they are both scalars!).

Matrix subtraction is similar. As an example,

? 16 93
? -I= ? 06 92
? . 3 Note that this gives an example where we have to figure out what size the identity matrix is. Since you can only add (or subtract)matrices of the same size, we conclude thatImust refer to a 2×2 identity matrix. Matrix addition is commutative,i.e.,ifAandBare matrices of the same size, then A+B=B+A. It"s also associative,i.e.,(A+B)+C=A+(B+C), so we write both as A+B+C. We always haveA+0=0+A=A,i.e., adding the zero matrix to a matrix has no effect.

Scalar multiplication

Another operation isscalar multiplication: multiplying a matrix by a scalar (i.e.,number), which is done by multiplying every entry of the matrix by the scalar. Scalar multiplication is usually denoted by juxtaposition, with the scalar on the left, as in (-2) ? ? ? 16 93
60
? ? ? = ? ? ? -2-12 -18-6 -12 0 ? ? ? . Scalar multiplication obeys several laws you can figure out for yourself,e.g.,ifAis any matrix andα,βare any scalars, then (α+β)A=αA+βA. It"s useful to identify the symbols appearing in this formula. The + symbol on the left is addition of scalars, while the + symbol on the right denotes matrix addition. Another simple property is (αβ)A=(α)(βA), whereαandβare scalars andAis a matrix. On the left hand side we see scalar-scalar multiplication (αβ)and scalar-matrix multiplication; on the right we see two cases of scalar-matrix multiplication. Note that 0·A= 0 (where the lefthand zero is the scalar zero, and the righthand zero is a matrix zero of the same size asA).

Matrix multiplication

It"s also possible to multiply two matrices usingmatrix multiplication. You can multiply two matricesAandBprovided their dimensions arecompatible, which means the number of columns ofAequals the number of rows ofB. SupposeAandBare compatible,i.e.,A has sizem×pandBhas sizep×n. The product matrixC=AB, which has sizem×n,is defined by C ij = p ? k=1 A ik B kj =A i1 B 1j +···+A ip B pj ,i=1,...,m, j=1,...,n. This rule looks complicated, but there are several ways to remember it. To find thei,jentry of the productC=AB, you need to know theith row ofAand thejth column ofB.The summation above can be interpreted as 'moving left to right along theirow ofA" while moving 'top to bottom" down thejth column ofB. As you go, you keep a running sum of the product of entries: one fromAand one fromB. 4 Now we can explain why the identity is called the identity: ifAis anym×nmatrix, thenAI=AandIA=A,i.e., when you multiply a matrix by an identity matrix, it has no effect. (The identity matrices in the formulasAI=AandIA=Ahave different sizes - what are they?) One very important fact about matrix multiplication is that it is (in general)not com- mutative:wedon"t(in general)haveAB=BA. In fact,BAmay not even make sense, or, if it makes sense, may be a different size thanAB(so that equality inAB=BAis mean- ingless). For example, ifAis 2×3andBis 3×4, thenABmakes sense (the dimensions are compatible)butBAdoesn"t even make sense (much less equalAB).EvenwhenAB andBAboth make sense and are the same size,i.e.,whenAandBare square, we don"t (in general)haveAB=BA. As a simple example, consider: ? 16 93
?? 0-1 -12 ? = ? -611 -3-3 ? , ? 0-1 -12 ?? 16 93
? = ? -9-3 17 0 ? . Matrix multiplicationisassociative,i.e.,(AB)C=A(BC)(provided the products make sense). Therefore we write the product simply asABC. Matrix multiplication is also associative with scalar multiplication,i.e.,α(AB)=(αA)B, whereαis a scalar andAandBare matrices (that can be multiplied). Matrix multiplication distributes across matrix addition:A(B+C)=AB+ACand (A+B)C=AC+BC.

Matrix-vector product

A very important and common case of matrix multiplication isy=Ax,whereAis anm×n matrix,xis ann-vector, andyis anm-vector. We can think of matrix vector multiplication (with anm×nmatrix)as a function that transformsn-vectors intom-vectors. The formula is y i =A i1 x 1 +···+A in x n ,i=1,...,m

Inner product

Another important special case of matrix multiplication occurs whenvis a row vector and wis a column vector (of the same size). Thenvwmakes sense, and has size 1×1,i.e.,isa scalar:vw=v 1 w 1 +···+v n w n . This occurs often in the formx T ywherexandyare both n-vectors. In this case the product (which is a number)is called theinner productordot productof the vectorsxandy. Other notation for the inner product is?x,y?orx·y. The inner product of a vector with itself is the square of its (Euclidean)norm?x?: ?x?= ? x 21
+x 22
+···+x 2n =⎷x T x.

Matrix powers

When a matrixAis square, then it makes sense to multiplyAby itself,i.e., to formA·A.

We refer to this matrix asA

2 . Similarly,kcopies ofAmultiplied together is denotedA k . 5 (Non-integer powers, such asA 1/2 (the matrix squareroot), are pretty tricky - they might not make sense, or be ambiguous, unless certain conditions onAhold. This is an advanced topic in linear algebra.)

By convention we setA

0 =I.

Useful identities

We"ve already mentioned a handful of matrix identities, that you could figure out yourself, e.g.,A+0=A. Here we list a few others, that are not hard to derive, and quite useful.

•transpose of product: (AB)

T =B T A T

•transpose of sum: (A+B)

T =A T +B T

•products of powers:A

k A l =A k+l (fork,l≥1 in general, and for allk,lifAis invertible)

Block matrices and submatrices

In some applications it"s useful to form matrices whose entries are themselves matrices, as in ? ABC ? , ? FI 0G ? , whereA,B,C,F,andGare matrices (as are 0 andI). Such matrices are calledblock matrices; the entriesA,B, etc. are called 'blocks" and are sometimes named by indices. Thus,Fis called the 1,1 block of the second matrix. Of course the block matrices must have the right dimensions to be able to fit together: matrices in the same (block)row must have the same number of rows (i.e., the same 'height"); matrices in the same (block)column must have the same number of columns (i.e.,thesame 'width"). Thus in the examples above,A,BandCmusthavethesamenumberofrows(e.g., they could be 2×3, 2×2, and 2×1). The second example is more interesting. Suppose thatFism×n. Then the identity matrix in the 2,2 position must have sizem×m(since it must have the same number of rows asF). We also see thatGmust havemcolumns, say, dimensionsp×m. That fixes the dimensions of the 0 matrix in the 2,1block-itmustbe p×m. You can also divide a larger matrix (or vector)into 'blocks". In this context the blocks are sometimes calledsubmatricesof the big matrix.

As a specific example, suppose that

C= ? 22
13 ? ,D= ? 023
547
? .

Then we have

? DC ? = ? 02322
54713
? . 6 It"s often useful to write anm×nmatrix as a 1×nblock matrix ofm-vectors (which are just its columns), or as anm×1 block matrix ofn-row-vectors (which are its rows). Block matrices can be added and multiplied as if the entries were numbers, provided the corresponding entries have the right sizes (i.e., 'conform")and you"re careful about the order of multiplication. Thus we have ? AB CD ?? X Y ? = ? AX+BY CX+DY ? provided the productsAX,BY,CX,andDYmakes sense.

3 Cost of basic matrix operations

Complexity analysis via flop count

The cost of a numerical linear algebra algorithm is often expressed by giving the total number offloating-point operationsorflopsrequired to carry it out, as a function of various problem dimensions. We define a flop as one addition, subtraction, multiplication, or division of two floating-point numbers. (Some authors define a flop as one multiplication followed by one addition, so their flop counts are smaller by a factor up to two.)To evaluate the complexity of an algorithm, we count the total number of flops, express it as a function (usually a polynomial)of the dimensions of the matrices and vectors involved, and simplify the expression by ignoring all terms except the leading (i.e., highest order or dominant) terms. As an example, suppose that a particular algorithm requires a total of m 3 +3m 2 n+mn+4mn 2 +5m+22 flops, wheremandnare problem dimensions. We would normally simplify this flop count to m 3 +3m 2 n+4mn 2 flops, since these are the leading terms in the problem dimensionsmandn. If in addition we assumed thatm?n, we would further simplify the flop count to 4mn 2 . Flop counts were originally popularized when floating-point operations were relatively slow, so counting the number gave a good estimate of the total computation time. This is no longer the case: Issues such as cache boundaries and locality of reference can dramatically affect the computation time of a numerical algorithm. However, flop counts can still give us a good rough estimate of the computation time of a numerical algorithm, and how the time grows with increasing problem size. Since a flop count no longer accurately predicts the computation time of an algorithm, we usually pay most attention to its order or orders, i.e., its largest exponents, and ignore differences in flop counts smaller than a factor of two or so. For example, an algorithm with flop count 5n 2 is considered comparable to one with aflopcount4n 2 , but faster than an algorithm with flop count (1/3)n 3 . 7

Vector operations

To compute the inner productx

T yof two vectorsx,y?R n we form the productsx i y i , and then add them, which requiresnmultiplies andn-1 additions, or 2n-1 flops. As mentioned above, we keep only leading term, and say that the inner product requires 2n flops, or even more approximately, ordernflops. A scalar-vector multiplicationαx,where

α?Randx?R

n costsnflops. The additionx+yof two vectorsx,y?R n also costsn flops. If the vectorsxandyare sparse,i.e., have only a few nonzero terms, these basic op- erations can be carried out faster (assuming the vectors are stored using an appropriate data structure). For example, ifxis a sparse vector withNnonzero entries, then the inner productx T ycan be computed in 2Nflops.

Matrix-vector multiplication

A matrix-vector multiplicationy=AxwhereA?R

m×n costs 2mnflops: wehaveto calculatemcomponents ofy, each of which is the product of a row ofAwithx,i.e.,an inner product of two vectors inR n . Matrix-vector products can often be accelerated by taking advantage of structure inA. For example, ifAis diagonal, thenAxcan be computed innflops, instead of 2n 2 flops for multiplication by a generaln×nmatrix. More generally, ifAis sparse, with onlyNnonzero elements (out ofmn),then2Nflops are needed to formAx, since we can skip multiplications and additions with zero. As a less obvious example, suppose the matrixAis represented (stored)in the factored formA=UV,whereU?R m×p ,V?R p×n ,andp?m,p?n. Then we can compute Axby first computingVx(which costs 2pnflops), and then computingU(Vx)(which costs

2mpflops),sothetotalis2p(m+n)flops. Sincep?min{m,n}, this is small compared to

2mn.

Matrix-matrix multiplication

The matrix-matrix productC=AB,whereA?R

m×n andB?R n×p ,costs2mnpflops. We havempelements inCto calculate, each of which is an inner product of two vectors of lengthn. Again, we can often make substantial savings by taking advantage of structure inAandB. For example, ifAandBare sparse, we can accelerate the multiplication by skipping additions and multiplications with zero. Ifm=pand we know thatCis symmetric, then we can calculate the matrix product inm 2 nflops, since we only have to compute the (1/2)m(m+ 1)in the lower triangular part. To form the product of several matrices, we can carry out the matrix-matrix multiplica- tions in different ways, which have different flop counts in general. The simplest example is computing the productD=ABC,whereA?R m×n ,B?R n×p ,andC?R p×q .Herewe can computeDin two ways, using matrix-matrix multiplies. One method is to first form the productAB(2mnpflops), and then formD=(AB)C(2mpqflops), so the total is

2mp(n+q)flops. Alternatively, we can first form the productBC(2npqflops), and then

formD=A(BC)(2mnqflops), with a total of 2nq(m+p)flops. The first method is better 8 when 2mp(n+q)<2nq(m+p),i.e.,when 1 n+1q<1m+1p. This assumes that no structure of the matrices is exploited in carrying out matrix-matrix products. For products of more than three matrices, there are many ways to parse the product into matrix-matrix multiplications. Although it is not hard to develop an algorithm that determines the best parsing (i.e., the one with the fewest required flops)given the matrix dimensions, in most applications the best parsing is clear. 9