Matrices

Dmytro Matsypura

QBUS1040
University of Sydney

Semester 2, 2020

Source: Introduction to Applied Linear Algebra, Boyd & Vandenberghe

[Link], QBUS1040 1/27

 Outline

Matrices

Matrix-vector multiplication

Examples

Matrices 2/27
 Matrices

• a matrix is a rectangular array of numbers, e.g.,

 
0.0 1.0 −2.3 0.1
1.3 4.0 0.1 0.0
4.1 −1.0 0.0 1.7

• its size is given by (row dimension) × (column dimension) e.g., matrix

above is 3 × 4

• elements also called entries or coefficients

• Bij is i, j element of matrix B

• i is the row index, j is the column index; indices start at 1

• two matrices are equal (denoted with “=”) if they are the same size and
corresponding entries are equal

Matrices 3/27
 Matrix shapes

an m × n matrix A is

• tall if m > n

• wide if m < n

• square if m = n

Matrices 4/27
 Column and row vectors

• we consider an n × 1 matrix to be an n-vector

• we consider a 1 × 1 matrix to be a number

• a 1 × n matrix is called a row vector, e.g.,

 
1.2 −0.3 1.4 2.6

which is not the same as the (column) vector

 
1.2
−0.3
 
 1.4
2.6

Matrices 5/27
 Columns and rows of a matrix

• suppose A is an m × n matrix with entries Aij for i = 1, . . . , m,

j = 1, . . . , n
• its jth column is (the m-vector)
 
A1j
 .. 
 . 
Amj
• its ith row is (the n-row-vector)
 
Ai1 ··· Ain
• slice of matrix: Ap:q,r:s is the (q − p + 1) × (s − r + 1) matrix

···
 
Apr Ap,r+1 Aps
Ap+1,r Ap+1,r+1 · · · Ap+1,s 
Ap:q,r:s =  .
 
.. .. 
 .. . . 
Aq,r Aq,r+1 ··· Aq,s

Matrices 6/27
 Block matrices

• we can form block matrices, whose entries are matrices, such as

 
B C
A=
D E

where B, C, D, and E are matrices (called submatrices or blocks of A)

• matrices in each block row must have same height (row dimension)

• matrices in each block column must have same width (column dimension)

• example: if
   
    2 2 1 4
B= 0 2 3 , C = −1 , D= , E=
1 3 5 4

then  
  0 2 3 −1
B C
=2 2 1 4
D E
1 3 5 4

Matrices 7/27
 Column and row representation of a matrix

• A is an m × n matrix

• can express as block matrix with its (m-vector) columns a1 , . . . , an

 
A = a1 a2 · · · an

• or as block matrix with its (n-row-vector) rows b1 , . . . , bm

 
b1
 b2 
A= . 
 
 .. 
bm

Matrices 8/27
 Examples

• image: Xij is i, j pixel value in a monochrome image

• rainfall data: Aij is rainfall at location i on day j

• multiple asset returns: Rij is return of asset j in period i

• contingency table: Aij is number of objects with first attribute i and

second attribute j

• feature matrix: Xij is value of feature i for entity j

in each of these, what do the rows and columns mean?

Matrices 9/27
 Graph or relation

• a relation is a set of pairs of objects, labeled 1, . . . , n, such as

R = {(1, 2), (1, 3), (2, 1), (2, 4), (3, 4), (4, 1)}

• same as directed graph

• can be represented as n × n matrix with Aij = 1 if (i, j) ∈ R

 
0 1 1 0
1 0 0 1
A=  
0 0 0 1
1 0 0 0

Matrices 10/27
 Special matrices

• m × n zero matrix has all entries zero, written as 0m×n or just 0

• identity matrix is square matrix with Iii = 1 and Iij = 0 for i 6= j, e.g.,
 
  1 0 0 0
1 0 0 1 0 0 
,  
0 1 0 0 1 0 
0 0 0 1

• a matrix is sparse if most (almost all) of its entries are zero

– can be stored and manipulated efficiently
– sparse matrix storage formats and algorithms exploit sparsity
– efficiency depends on number of nonzeros and their positions
– nnz(A) is number of nonzero entries
– positions of nonzeros are visualized in a ‘spy plot’
– examples: 0 and I

Matrices 11/27
 Example of a spy plot
The matrix below has 3600 entries with 180 nonzeros.

Matrices 12/27
 Diagonal and triangular matrices

• diagonal matrix: square matrix with Aij = 0 when i 6= j

• diag(a1 , . . . , an ) denotes the diagonal matrix with Aii = ai for

i = 1, . . . , n

• example:
 
0.2 0 0
diag(0.2, −3, 1.2) =  0 −3 0
0 0 1.2

• lower triangular matrix: Aij = 0 for i < j

• upper triangular matrix: Aij = 0 for i > j

• examples:
 
1 −1 0.7  
−0.6 0
0 1.2 −1.1 (upper triangular), (lower triangular)
−0.3 3.5
0 0 3.2

Matrices 13/27
 Transpose

• the transpose of an m × n matrix A is denoted AT , and defined by

(AT )ij = Aji , i = 1, . . . , n, j = 1, . . . , m

• for example:
 
0 4  
0 7 3
A = 7 0 ; AT = .
4 0 1
3 1
• transposition converts row vectors into column vectors and vice versa
• (AT )T = A

Matrices 14/27
 Addition, subtraction, and scalar multiplication

• (just like vectors) we can add or subtract matrices of the same size:

(A + B)ij = Aij + Bij , i = 1, . . . , m, j = 1, . . . , n

(subtraction is similar)

• scalar multiplication:

(αA)ij = αAij , i = 1, . . . , m, j = 1, . . . , n

• many obvious properties, e.g.,

A + B = B + A, α(A + B) = αA + αB, (A + B)T = AT + B T

Matrices 15/27
 Matrix norm

• for m × n matrix A, we define

m X
n
!1/2
X
kAk = A2ij
i=1 j=1

• often called Frobenius norm, denoted kAkF

• agrees with vector norm when n = 1

• satisfies norm properties:

kαAk = |α|kAk
kA + Bk ≤ kAk + kBk
kAk ≥ 0
kAk = 0 only if A=0

• distance between two matrices: kA − Bk

• (there are lots of other matrix norms, which we won’t use)

Matrices 16/27
 Outline

Matrices

Matrix-vector multiplication

Examples

Matrices 17/27
 Matrix-vector product

• matrix-vector product of m × n matrix A, n-vector x, denoted y = Ax,

with
yi = Ai1 x1 + · · · + Ain xn , i = 1, . . . , m

• for example,
 
  2  
0 2 −1   3
1 =
−2 1 1 −4
−1

Matrices 18/27
 Row interpretation

• y = Ax can be expressed as

yi = bTi x, i = 1, . . . , m

where bT1 , . . . , bTm are rows of A

• so y = Ax is a ‘batch’ inner product of all rows of A with x

• example: A1 is vector of row sums of matrix A

Matrices 19/27
 Column interpretation

• y = Ax can be expressed as

y = x1 a1 + x2 a2 + · · · + xn an

where a1 , . . . , an are columns of A

• so y = Ax is a linear combination of columns of A, with coefficients

x1 , . . . , x n

• important example: Aej = aj

• columns of A are linearly independent if Ax = 0 implies x = 0

Matrices 20/27
 Outline

Matrices

Matrix-vector multiplication

Examples

Matrices 21/27
 General examples

• 0x = 0, i.e., multiplying by zero matrix gives zero

• Ix = x, i.e., multiplying by identity matrix does nothing

• inner product aT b is matrix-vector product of 1 × n matrix aT and

n-vector b

• x̃ = Ax is de-meaned version of x, with

1 − 1/n −1/n ··· −1/n

 
 −1/n 1 − 1/n ··· −1/n 
A=
 
.. .. .. 
 . . . 
−1/n −1/n ··· 1 − 1/n

Matrices 22/27
 Difference matrix

• (n − 1) × n difference matrix is

−1 1 0 ··· 0 0 0
 
0 −1 1 ··· 0 0 0
 
 .. .. 
 . . 
D= 
 .. .. 

 . . 

0 0 0 ··· −1 1 0
0 0 0 ··· 0 −1 1

y = Dx is (n − 1)-vector of differences of consecutive entries of x:

x2 − x1
 
 x3 − x2 
Dx = 
 
.. 
 . 
xn − xn−1

• Dirichlet energy: kDxk2 is a measure of wiggliness for x a time series

Matrices 23/27
 Return matrix - portfolio vector

• R is T × n matrix of asset returns

• Rij is return of asset j in period i (say, in percentage)

• n-vector w gives portfolio (investments in the assets)

• T -vector Rw is time series of the portfolio return

• avg(Rw) is the portfolio (mean) return, std(Rw) is its risk

Matrices 24/27
 Feature matrix - weight vector

• X = [x1 · · · xN ] is n × N feature matrix

• column xj is feature n-vector for object or example j

• Xij is value of feature i for example j

• n-vector w is weight vector

• s = X T w is vector of scores for each example; sj = xTj w

Matrices 25/27
 Input - output matrix

• A is m × n matrix

• y = Ax

• n-vector x is input or action

• m-vector y is output or result

• Aij is the factor by which yi depends on xj

• Aij is the gain from input j to output i

• e.g., if A is lower triangular, then yi only depends on x1 , . . . , xi

Matrices 26/27
 Complexity of matrix operations

• m × n matrix A stored as m × n array of numbers

(for sparse A, store only nnz(A) nonzero values)

• matrix addition, scalar-matrix multiplication cost mn flops

• matrix-vector multiplication costs m(2n − 1) ≈ 2mn flops

(for sparse A, around 2nnz(A) flops)

Matrices 27/27