n, we shall denote by v(i1 : i2 ) the vector of size i2 ’ i1 + 1 made up by

the i1 -th to the i2 -th components of v.

These notations are convenient in view of programming the algorithms

that will be presented throughout the volume in the MATLAB language.

1.3 Operations with Matrices 5

1.3 Operations with Matrices

Let A = (aij ) and B = (bij ) be two matrices m — n over K. We say that

A is equal to B, if aij = bij for i = 1, . . . , m, j = 1, . . . , n. Moreover, we

de¬ne the following operations:

- matrix sum: the matrix sum is the matrix A+B = (aij +bij ). The neutral

element in a matrix sum is the null matrix, still denoted by 0 and

made up only by null entries;

- matrix multiplication by a scalar: the multiplication of A by » ∈ K, is a

matrix »A = (»aij );

- matrix product: the product of two matrices A and B of sizes (m, p)

and (p, n) respectively, is a matrix C(m, n) whose entries are cij =

p

aik bkj , for i = 1, . . . , m, j = 1, . . . , n.

k=1

The matrix product is associative and distributive with respect to the ma-

trix sum, but it is not in general commutative. The square matrices for

which the property AB = BA holds, will be called commutative.

In the case of square matrices, the neutral element in the matrix product

is a square matrix of order n called the unit matrix of order n or, more

frequently, the identity matrix given by In = (δij ). The identity matrix

is, by de¬nition, the only matrix n — n such that AIn = In A = A for all

square matrices A. In the following we shall omit the subscript n unless it

is strictly necessary. The identity matrix is a special instance of a diagonal

matrix of order n, that is, a square matrix of the type D = (dii δij ). We will

use in the following the notation D = diag(d11 , d22 , . . . , dnn ).

Finally, if A is a square matrix of order n and p is an integer, we de¬ne Ap

as the product of A with itself iterated p times. We let A0 = I.

Let us now address the so-called elementary row operations that can be

performed on a matrix. They consist of:

- multiplying the i-th row of a matrix by a scalar ±; this operation is

equivalent to pre-multiplying A by the matrix D = diag(1, . . . , 1, ±,

1, . . . , 1), where ± occupies the i-th position;

- exchanging the i-th and j-th rows of a matrix; this can be done by pre-

multiplying A by the matrix P(i,j) of elements

±

1 if r = s = 1, . . . , i ’ 1, i + 1, . . . , j ’ 1, j + 1, . . . n,

(i,j)

1 if r = j, s = i or r = i, s = j,

prs = (1.2)

0 otherwise,

6 1. Foundations of Matrix Analysis

where Ir denotes the identity matrix of order r = j ’ i ’ 1 if j >

i (henceforth, matrices with size equal to zero will correspond to

the empty set). Matrices like (1.2) are called elementary permutation

matrices. The product of elementary permutation matrices is called

a permutation matrix, and it performs the row exchanges associated

with each elementary permutation matrix. In practice, a permutation

matrix is a reordering by rows of the identity matrix;

- adding ± times the j-th row of a matrix to its i-th row. This operation

(i,j)

can also be performed by pre-multiplying A by the matrix I + N± ,

(i,j)

where N± is a matrix having null entries except the one in position

i, j whose value is ±.

1.3.1 Inverse of a Matrix

De¬nition 1.6 A square matrix A of order n is called invertible (or regular

or nonsingular) if there exists a square matrix B of order n such that

A B = B A = I. B is called the inverse matrix of A and is denoted by A’1 .

A matrix which is not invertible is called singular.

If A is invertible its inverse is also invertible, with (A’1 )’1 = A. Moreover,

if A and B are two invertible matrices of order n, their product AB is also

invertible, with (A B)’1 = B’1 A’1 . The following property holds.

Property 1.2 A square matrix is invertible i¬ its column vectors are lin-

early independent.

De¬nition 1.7 We call the transpose of a matrix A∈ Rm—n the matrix

n — m, denoted by AT , that is obtained by exchanging the rows of A with

the columns of A.

Clearly, (AT )T = A, (A + B)T = AT + BT , (AB)T = BT AT and (±A)T =

±AT ∀± ∈ R. If A is invertible, then also (AT )’1 = (A’1 )T = A’T .

De¬nition 1.8 Let A ∈ Cm—n ; the matrix B = AH ∈ Cn—m is called the

conjugate transpose (or adjoint) of A if bij = aji , where aji is the complex

¯ ¯

conjugate of aji .

In analogy with the case of the real matrices, it turns out that (A+B)H =

AH + BH , (AB)H = BH AH and (±A)H = ±AH ∀± ∈ C.

¯

De¬nition 1.9 A matrix A ∈ Rn—n is called symmetric if A = AT , while

it is antisymmetric if A = ’AT . Finally, it is called orthogonal if AT A =

AAT = I, that is A’1 = AT .

Permutation matrices are orthogonal and the same is true for their prod-

ucts.

1.3 Operations with Matrices 7

De¬nition 1.10 A matrix A ∈ Cn—n is called hermitian or self-adjoint if

¯

AT = A, that is, if AH = A, while it is called unitary if AH A = AAH = I.

Finally, if AAH = AH A, A is called normal.

As a consequence, a unitary matrix is one such that A’1 = AH .

Of course, a unitary matrix is also normal, but it is not in general her-

mitian. For instance, the matrix of the Example 1.4 is unitary, although

not symmetric (if s = 0). We ¬nally notice that the diagonal entries of an

hermitian matrix must necessarily be real (see also Exercise 5).

1.3.2 Matrices and Linear Mappings

De¬nition 1.11 A linear map from Cn into Cm is a function f : Cn ’’

Cm such that f (±x + βy) = ±f (x) + βf (y), ∀±, β ∈ K and ∀x, y ∈ Cn .

The following result links matrices and linear maps.

Property 1.3 Let f : Cn ’’ Cm be a linear map. Then, there exists a

unique matrix Af ∈ Cm—n such that

∀x ∈ Cn .

f (x) = Af x (1.3)

Conversely, if Af ∈ Cm—n then the function de¬ned in (1.3) is a linear

map from Cn into Cm .

Example 1.4 An important example of a linear map is the counterclockwise

rotation by an angle ‘ in the plane (x1 , x2 ). The matrix associated with such a

map is given by

c s

G(‘) = , c = cos(‘), s = sin(‘)

’s c

•

and it is called a rotation matrix.

1.3.3 Operations with Block-Partitioned Matrices

All the operations that have been previously introduced can be extended

to the case of a block-partitioned matrix A, provided that the size of each

single block is such that any single matrix operation is well-de¬ned.

Indeed, the following result can be shown (see, e.g., [Ste73]).

Property 1.4 Let A and B be the block matrices

® ®

A11 . . . A1l B11 . . . B1n

. . , B = . .

A=° . .. ..

.» °. .»

. .

. . . .

Ak1 . . . Akl Bm1 . . . Bmn

where Aij and Bij are matrices (ki — lj ) and (mi — nj ). Then we have

8 1. Foundations of Matrix Analysis

1.

® ®

AT AT

»A11 ... »A1l ...

11 k1

. . , . . ;

.. ..

» ∈ C; A = ° .

»A = ° . .» .»

T

. .

. . . .

AT AT

»Ak1 ... »Akl ...

1l kl

2. if k = m, l = n, mi = ki and nj = lj , then

®

A11 + B11 . . . A1l + B1l

. .

..

A+B=° »;

. .

.

. .

Ak1 + Bk1 . . . Akl + Bkl

m

3. if l = m, li = mi and ki = ni , then, letting Cij = Ais Bsj ,

s=1

®

C11 ... C1l

. . .

..

AB = ° . .»

.

. .

Ck1 ... Ckl

1.4 Trace and Determinant of a Matrix

Let us consider a square matrix A of order n. The trace of a matrix is the

n

sum of the diagonal entries of A, that is tr(A) = aii .

i=1

We call the determinant of A the scalar de¬ned through the following for-

mula

det(A) = sign(π)a1π1 a2π2 . . . anπn ,

π∈P

where P = π = (π1 , . . . , πn )T is the set of the n! vectors that are ob-

tained by permuting the index vector i = (1, . . . , n)T and sign(π) equal to

1 (respectively, ’1) if an even (respectively, odd) number of exchanges is

needed to obtain π from i.

The following properties hold

det(A) = det(AT ), det(AB) = det(A)det(B), det(A’1 ) = 1/det(A),

det(AH ) = det(A), det(±A) = ±n det(A), ∀± ∈ K.

Moreover, if two rows or columns of a matrix coincide, the determinant

vanishes, while exchanging two rows (or two columns) produces a change

1.5 Rank and Kernel of a Matrix 9

of sign in the determinant. Of course, the determinant of a diagonal matrix

is the product of the diagonal entries.

Denoting by Aij the matrix of order n ’ 1 obtained from A by elimi-

nating the i-th row and the j-th column, we call the complementary minor

associated with the entry aij the determinant of the matrix Aij . We call

the k-th principal (dominating) minor of A, dk , the determinant of the

principal submatrix of order k, Ak = A(1 : k, 1 : k). If we denote by

∆ij = (’1)i+j det(Aij ) the cofactor of the entry aij , the actual computa-

tion of the determinant of A can be performed using the following recursive

relation

±

a11 if n = 1,

det(A) = (1.4)

n

∆ij aij , for n > 1,

j=1

which is known as the Laplace rule. If A is a square invertible matrix of

order n, then

1

A’1 = C

det(A)

where C is the matrix having entries ∆ji , i, j = 1, . . . , n.

As a consequence, a square matrix is invertible i¬ its determinant is non-

vanishing. In the case of nonsingular diagonal matrices the inverse is still

a diagonal matrix having entries given by the reciprocals of the diagonal

entries of the matrix.

Every orthogonal matrix is invertible, its inverse is given by AT , moreover

det(A) = ±1.

1.5 Rank and Kernel of a Matrix

Let A be a rectangular matrix m — n. We call the determinant of order

q (with q ≥ 1) extracted from matrix A, the determinant of any square

matrix of order q obtained from A by eliminating m ’ q rows and n ’ q

columns.

De¬nition 1.12 The rank of A (denoted by rank(A)) is the maximum

order of the nonvanishing determinants extracted from A. A matrix has

complete or full rank if rank(A) = min(m,n).

Notice that the rank of A represents the maximum number of linearly

independent column vectors of A that is, the dimension of the range of A,

de¬ned as

range(A) = {y ∈ Rm : y = Ax for x ∈ Rn } . (1.5)

10 1. Foundations of Matrix Analysis

Rigorously speaking, one should distinguish between the column rank of A

and the row rank of A, the latter being the maximum number of linearly

independent row vectors of A. Nevertheless, it can be shown that the row

rank and column rank do actually coincide.

The kernel of A is de¬ned as the subspace

ker(A) = {x ∈ Rn : Ax = 0} .

The following relations hold

T H

(if A ∈ Cm—n , rank(A) = rank(A ))

1. rank(A) = rank(A )

2. rank(A) + dim(ker(A)) = n.

In general, dim(ker(A)) = dim(ker(AT )). If A is a nonsingular square ma-

trix, then rank(A) = n and dim(ker(A)) = 0.

Example 1.5 Let

1 1 0

A= .

’1

1 1

•

Then, rank(A) = 2, dim(ker(A)) = 1 and dim(ker(AT )) = 0.

We ¬nally notice that for a matrix A ∈ Cn—n the following properties are

equivalent:

1. A is nonsingular;

2. det(A) = 0;

3. ker(A) = {0};

4. rank(A) = n;

5. A has linearly independent rows and columns.

1.6 Special Matrices

1.6.1 Block Diagonal Matrices

These are matrices of the form D = diag(D1 , . . . , Dn ), where Di are square

matrices with i = 1, . . . , n. Clearly, each single diagonal block can be of

di¬erent size. We shall say that a block diagonal matrix has size n if n

is the number of its diagonal blocks. The determinant of a block diagonal

matrix is given by the product of the determinants of the single diagonal

blocks.

1.6 Special Matrices 11

1.6.2 Trapezoidal and Triangular Matrices

A matrix A(m — n) is called upper trapezoidal if aij = 0 for i > j, while it

is lower trapezoidal if aij = 0 for i < j. The name is due to the fact that,

in the case of upper trapezoidal matrices, with m < n, the nonzero entries

of the matrix form a trapezoid.

A triangular matrix is a square trapezoidal matrix of order n of the form

® ®

l11 0 . . . 0 u11 u12 . . . u1n

l21 l22 . . . 0 0 u22 . . . u2n

L= . . or U = . . .

. .

°. .» °. .»

. .

. . . . . .

ln1 ln2 ... lnn 0 0 ... unn

The matrix L is called lower triangular while U is upper triangular.

Let us recall some algebraic properties of triangular matrices that are easy

to check.

- The determinant of a triangular matrix is the product of the diagonal

entries;

- the inverse of a lower (respectively, upper) triangular matrix is still lower

(respectively, upper) triangular;

- the product of two lower triangular (respectively, upper trapezoidal) ma-

trices is still lower triangular (respectively, upper trapezodial);

- if we call unit triangular matrix a triangular matrix that has diagonal

entries equal to 1, then, the product of lower (respectively, upper) unit

triangular matrices is still lower (respectively, upper) unit triangular.

1.6.3 Banded Matrices

The matrices introduced in the previous section are a special instance of

banded matrices. Indeed, we say that a matrix A ∈ Rm—n (or in Cm—n )

has lower band p if aij = 0 when i > j + p and upper band q if aij = 0

when j > i+q. Diagonal matrices are banded matrices for which p = q = 0,

while trapezoidal matrices have p = m’1, q = 0 (lower trapezoidal), p = 0,

q = n ’ 1 (upper trapezoidal).

Other banded matrices of relevant interest are the tridiagonal matrices

for which p = q = 1 and the upper bidiagonal (p = 0, q = 1) or lower bidiag-

onal (p = 1, q = 0). In the following, tridiagn (b, d, c) will denote the triadi-

agonal matrix of size n having respectively on the lower and upper principal

diagonals the vectors b = (b1 , . . . , bn’1 )T and c = (c1 , . . . , cn’1 )T , and on

the principal diagonal the vector d = (d1 , . . . , dn )T . If bi = β, di = δ and

ci = γ, β, δ and γ being given constants, the matrix will be denoted by

tridiagn (β, δ, γ).

12 1. Foundations of Matrix Analysis

We also mention the so-called lower Hessenberg matrices (p = m ’ 1,

q = 1) and upper Hessenberg matrices (p = 1, q = n ’ 1) that have the

following structure

® ®

0

h11 h12 h11 h12 ... h1n

h21 h22 h2n

h21 h22 . . .

H= . or H = . .

.. ..

.

.. . . .»

°. . hm’1n » °

.

0 hmn’1 hmn

hm1 . . . . . . hmn

Matrices of similar shape can obviously be set up in the block-like format.

1.7 Eigenvalues and Eigenvectors

Let A be a square matrix of order n with real or complex entries; the number

» ∈ C is called an eigenvalue of A if there exists a nonnull vector x ∈ Cn

such that Ax = »x. The vector x is the eigenvector associated with the

eigenvalue » and the set of the eigenvalues of A is called the spectrum of A,

denoted by σ(A). We say that x and y are respectively a right eigenvector

and a left eigenvector of A, associated with the eigenvalue », if