316

15.1 Basic de¬nitions and properties 317

rectangular array

«

···

a11 a12 a1n

···

¬ a21 a22 a2n ·

A=¬ . . ·,

¬ ·

.

. . .

. . .

am1 am2 · · · amn

where each entry aij in the array is an element of R; the element aij is called

the (i, j) entry of A, which we may denote by A(i, j). For i = 1, . . . , m, the

ith row of A is

(ai1 , . . . , ain ),

which we may denote by A(i), and for j = 1, . . . , n, the jth column of A is

«

a1j

¬ a2j ·

¬ . ·,

¬ ·

. .

amj

which we may denote by A(·, j). We regard a row of A as a 1 — n matrix,

and a column of A as an m — 1 matrix.

The set of all m — n matrices over R is denoted by Rm—n . Elements of

R1—n are called row vectors (of dimension n) and elements of Rm—1

are called column vectors (of dimension m). Elements of Rn—n are

called square matrices (of dimension n). We do not make a distinction

between R1—n and R—n ; that is, we view standard n-tuples as row vectors.

Also, where there can be no confusion, we may interpret an element of R1—1

simply as an element of R.

We can de¬ne the familiar operations of scalar multiplication, addition,

and multiplication on matrices:

• If A ∈ Rm—n and c ∈ R, then cA is the m — n matrix whose (i, j)

entry is cA(i, j).

• If A, B ∈ Rm—n , then A + B is the m — n matrix whose (i, j) entry

is A(i, j) + B(i, j).

• If A ∈ Rm—n and B ∈ Rn—p , then AB is the m — p matrix whose

(i, k) entry is

n

A(i, j)B(j, k).

j=1

318 Matrices

We can also de¬ne the di¬erence A ’ B := A + (’1R )B of matrices of the

same dimension, which is the same as taking the di¬erence of corresponding

entries. These operations satisfy the usual properties:

Theorem 15.1. If A, B, C ∈ Rm—n , U, V ∈ Rn—p , Z ∈ Rp—q , and c, d ∈ R,

then

(i) c(dA) = (cd)A = d(cA),

(ii) (A + B) + C = A + (B + C),

(iii) A + B = B + A,

(iv) c(A + B) = cA + cB,

(v) (c + d)A = cA + dA,

(vi) (A + B)U = AU + BU ,

(vii) A(U + V ) = AU + AV ,

(viii) c(AU ) = (cA)U = A(cU ),

(ix) A(U Z) = (AU )Z.

Proof. All of these are trivial, except the last one which requires just a bit

of computation to show that the (i, ) entry of both A(U Z) and (AU )Z is

(verify)

p

n

A(i, j)U (j, k)Z(k, ). 2

j=1 k=1

Note that while matrix addition is commutative, matrix multiplication in

general is not.

Some simple but useful facts to keep in mind are the following:

• If A ∈ Rm—n and B ∈ Rn—p , then the kth column of AB is equal to

Av, where v = B(·, k); also, the ith row of AB is equal to wB, where

w = A(i).

• If A ∈ Rm—n and u = (u1 , . . . , um ) ∈ R1—m , then

m

uA = ui A(i).

i=1

In words: uA is a linear combination of the rows of A, with coe¬cients

taken from the corresponding entries of u.

• If A ∈ Rm—n and

«

v1

v = . ∈ Rn—1 ,

¬.·

.

vn

15.1 Basic de¬nitions and properties 319

then

n

Av = vj A(·, j).

j=1

In words: Av is a linear combination of the columns of A, with coef-

¬cients taken from the corresponding entries of v.

If A ∈ Rm—n , the transpose of A, denoted by A , is de¬ned to be the

n — m matrix whose (j, i) entry is A(i, j).

Theorem 15.2. If A, B ∈ Rm—n , C ∈ Rn—p , and c ∈ R, then

(i) (A + B) = A + B ,

(ii) (cA) = cA ,

(iii) (A ) = A,

(iv) (AC) = C A .

Proof. Exercise. 2

An n — n matrix A is called a diagonal matrix if A(i, j) = 0R for i = j,

which is to say that the entries o¬ the “main diagonal” of A are all zero. A

scalar matrix is a diagonal matrix whose diagonal entries are all the same.

The scalar matrix I, where all the entries on the main diagonal are 1R , is

called the n — n identity matrix. It is easy to see that if A is an n — n

matrix, then AI = IA = A. More generally, if B is an n — m matrix, then

IB = B, and if C is an m — n matrix, then CI = C.

If Ai is an ni — ni+1 matrix, for i = 1, . . . , k, then by associativity of

matrix multiplication (part (ix) of Theorem 15.1), we may write the product

matrix A1 · · · Ak , which is an n1 — nk+1 matrix, without any ambiguity. For

an n — n matrix A, and a positive integer k, we write Ak to denote the

product A · · · A, where there are k terms in the product. Note that A1 = A.

We may extend this notation to k = 0, de¬ning A0 to be the n — n identity

matrix.

One may readily verify the usual rules of exponent arithmetic: for non-

negative integers k1 , k2 , we have

(Ak1 )k2 = Ak1 k2 and Ak1 Ak2 = Ak1 +k2 .

It is easy also to see that part (iv) of Theorem 15.2 implies that for all

non-negative integers k, we have

(Ak ) = (A )k .

320 Matrices

Algorithmic issues

For computational purposes, matrices are represented in the obvious way as

arrays of elements of R. As remarked at the beginning of this chapter, we

shall treat R as an “abstract data type,” and not worry about how elements

of R are actually represented; in discussing the complexity of algorithms,

we shall simply count “operations in R,” by which we mean additions, sub-

tractions, multiplications; we shall sometimes also include equality testing

and computing multiplicative inverses as “operations in R.” In any real

implementation, there will be other costs, such as incrementing counters,

and so on, which we may safely ignore, as long as their number is at most

proportional to the number of operations in R.

The following statements are easy to verify:

• We can multiply an m — n matrix times a scalar using mn operations