Exercise 0.1: Computing with matrices: ten direct calculations

For each line, carry out the requested computation, then give the indicated entry or entries of the result. Entry $(i,j)$ is the one in row $i$ and column $j$ .

A single rule carries the whole chapter: entry $(i,j)$ of a product $PQ$ is obtained by running row $i$ of $P$ against column $j$ of $Q$ , term by term, then adding. Before computing, check the sizes: an $m\times n$ times an $n\times p$ gives an $m\times p$ . For a $2\times 2$ determinant, it is $ad-bc$ ; for a $3\times 3$ , expand along the first row with the signs $+$ , $-$ , $+$ .

a) $A=\begin{pmatrix} 3 & -1 \\ 2 & 5 \end{pmatrix}$ and $B=\begin{pmatrix} 1 & 4 \\ -2 & 0 \end{pmatrix}$ : compute $2A-B$ , then give its entries $(1,2)$ and $(2,1)$ .
b) $C=\begin{pmatrix} 2 & 0 & -3 \\ 1 & 4 & 5 \end{pmatrix}$ : write the transpose $C^{T}$ , then give its entries $(3,1)$ and $(1,2)$ .
c) $P=\begin{pmatrix} 2 & -3 \\ 1 & 4 \end{pmatrix}$ and $Q=\begin{pmatrix} 5 & 1 \\ -2 & 3 \end{pmatrix}$ : compute $PQ$ , then give its entries $(1,2)$ and $(2,1)$ .
d) $D=\begin{pmatrix} 1 & 2 & 0 \\ -1 & 3 & 2 \end{pmatrix}$ and $E=\begin{pmatrix} 2 & 1 \\ 0 & -1 \\ 4 & 3 \end{pmatrix}$ : compute $DE$ , then give its entries $(2,1)$ and $(2,2)$ .
e) $F=\begin{pmatrix} 1 & 0 & 2 \\ 3 & -1 & 1 \\ 0 & 2 & -2 \end{pmatrix}$ and $\vec{v}=\begin{pmatrix} 3 \\ -1 \\ 2 \end{pmatrix}$ : compute $F\vec{v}$ , then give its second and third components.
f) $M=\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$ is the adjacency matrix of a directed graph: compute $M^{2}$ , then give its entries $(2,2)$ and $(2,3)$ .
g) With the same matrix $M$ : compute $M^{3}$ , then give its entries $(1,3)$ and $(3,1)$ .
h) Compute $\det\begin{pmatrix} -4 & 5 \\ 3 & -6 \end{pmatrix}$ .
i) $G=\begin{pmatrix} 4 & 3 \\ 2 & 2 \end{pmatrix}$ : compute $G^{-1}$ , then give its entries $(1,2)$ and $(2,1)$ .
j) Compute $\det\begin{pmatrix} 2 & -1 & 3 \\ 1 & 0 & 4 \\ -2 & 1 & 1 \end{pmatrix}$ by cofactor expansion along the first row.

Type your answers, the page tells you right or wrong 0/18

a)

entry

(1,2)

entry

(2,1)

b)

entry

(3,1)

of

C^{T}

entry

(1,2)

of

C^{T}

c)

entry

(1,2)

entry

(2,1)

d)

entry

(2,1)

entry

(2,2)

e)

second component

third component

f)

entry

(2,2)

of

M^{2}

entry

(2,3)

of

M^{2}

g)

entry

(1,3)

of

M^{3}

entry

(3,1)

of

M^{3}

h)

determinant

i)

entry

(1,2)

of

G^{-1}

entry

(2,1)

of

G^{-1}

j)

determinant

Show the solution

Answers

a) $2A-B=\begin{pmatrix} 5 & -6 \\ 6 & 10 \end{pmatrix}$ ; $-6$ and $6$
b) $C^{T}=\begin{pmatrix} 2 & 1 \\ 0 & 4 \\ -3 & 5 \end{pmatrix}$ ; $-3$ and $1$
c) $PQ=\begin{pmatrix} 16 & -7 \\ -3 & 13 \end{pmatrix}$ ; $-7$ and $-3$
d) $DE=\begin{pmatrix} 2 & -1 \\ 6 & 2 \end{pmatrix}$ ; $6$ and $2$
e) $F\vec{v}=\begin{pmatrix} 7 \\ 12 \\ -6 \end{pmatrix}$ ; $12$ and $-6$
f) $M^{2}=\begin{pmatrix} 1 & 1 & 1 \\ 0 & 2 & 1 \\ 1 & 0 & 1 \end{pmatrix}$ ; $2$ and $1$
g) $M^{3}=\begin{pmatrix} 1 & 2 & 2 \\ 2 & 1 & 2 \\ 0 & 2 & 1 \end{pmatrix}$ ; $2$ and $0$
h) $(-4)(-6)-(5)(3)=9$
i) $G^{-1}=\begin{pmatrix} 1 & -\frac{3}{2} \\ -1 & 2 \end{pmatrix}$ ; $-\frac{3}{2}$ and $-1$
j) $2(-4)+1(9)+3(1)=4$

The move that decides everything: write down the size of the result BEFORE computing, then aim at the requested entry by its row and its column. A product is not computed by multiplying term by term; you run a row against a column.

a)

Term by term: $2A=\begin{pmatrix} 6 & -2 \\ 4 & 10 \end{pmatrix}$ , so $2A-B=\begin{pmatrix} 6-1 & -2-4 \\ 4-(-2) & 10-0 \end{pmatrix}=\begin{pmatrix} 5 & -6 \\ 6 & 10 \end{pmatrix}$ . Entries: $(1,2)=-6$ and $(2,1)=6$ . Pitfall: $4-(-2)=6$ , the double minus sign.

b)

The rows of $C$ become the columns: $C^{T}=\begin{pmatrix} 2 & 1 \\ 0 & 4 \\ -3 & 5 \end{pmatrix}$ , a $3\times 2$ matrix. Entries: $(C^{T})_{31}=C_{13}=-3$ and $(C^{T})_{12}=C_{21}=1$ . Pitfall: keeping the size $2\times 3$ and reading $(1,2)$ in $C$ , which gives $0$ .

c)

$PQ=\begin{pmatrix} 2(5)+(-3)(-2) & 2(1)+(-3)(3) \\ 1(5)+4(-2) & 1(1)+4(3) \end{pmatrix}=\begin{pmatrix} 16 & -7 \\ -3 & 13 \end{pmatrix}$ . Entries: $(1,2)=-7$ and $(2,1)=-3$ . Pitfall: multiplying term by term, which would give $(1,2)=-3$ .

d)

A $2\times 3$ times a $3\times 2$ gives a $2\times 2$ . Row 2 of $D$ , $(-1,3,2)$ , against column 1 of $E$ , $(2,0,4)$ : $-2+0+8=6$ ; against column 2, $(1,-1,3)$ : $-1-3+6=2$ . In full, $DE=\begin{pmatrix} 2 & -1 \\ 6 & 2 \end{pmatrix}$ . Pitfall: believing the result is $3\times 3$ , which is the size of $ED$ .

e)

Each row of $F$ against $\vec{v}$ : $1(3)+0(-1)+2(2)=7$ , $3(3)+(-1)(-1)+1(2)=12$ , $0(3)+2(-1)+(-2)(2)=-6$ . So $F\vec{v}=\begin{pmatrix} 7 \\ 12 \\ -6 \end{pmatrix}$ , second component $12$ , third $-6$ . Pitfall: $(-1)(-1)=+1$ in the second row.

f)

Each row of $M^{2}$ is the sum of the rows of $M$ picked out by the $1$ s of the starting row. Row 1: rows 2 and 3, $(1,1,1)$ . Row 2: rows 1 and 3, $(0,2,1)$ . Row 3: row 2, $(1,0,1)$ . So $M^{2}=\begin{pmatrix} 1 & 1 & 1 \\ 0 & 2 & 1 \\ 1 & 0 & 1 \end{pmatrix}$ , entries $(2,2)=2$ and $(2,3)=1$ . Pitfall: squaring each entry, which gives back $M$ .

g)

$M^{3}=M^{2}M$ : row 1 of $M^{2}$ , $(1,1,1)$ , adds up the three rows of $M$ , giving $(1,2,2)$ ; row 3, $(1,0,1)$ , adds up rows 1 and 3, giving $(0,2,1)$ . So $M^{3}=\begin{pmatrix} 1 & 2 & 2 \\ 2 & 1 & 2 \\ 0 & 2 & 1 \end{pmatrix}$ , entries $(1,3)=2$ and $(3,1)=0$ . The $0$ says that no path of length 3 leads from vertex 3 to vertex 1.

h)

$ad-bc=(-4)(-6)-(5)(3)=24-15=9$ . Pitfall: $-24-15=-39$ , losing the sign of the product of two negatives.

i)

$\det G=4(2)-3(2)=2$ . Swap the diagonal entries, change the sign of the off-diagonal entries, divide by $2$ : $G^{-1}=\frac{1}{2}\begin{pmatrix} 2 & -3 \\ -2 & 4 \end{pmatrix}=\begin{pmatrix} 1 & -\frac{3}{2} \\ -1 & 2 \end{pmatrix}$ . Entries: $(1,2)=-\frac{3}{2}$ and $(2,1)=-1$ . Pitfall: forgetting to divide by the determinant.

j)

$2\begin{vmatrix} 0 & 4 \\ 1 & 1 \end{vmatrix}-(-1)\begin{vmatrix} 1 & 4 \\ -2 & 1 \end{vmatrix}+3\begin{vmatrix} 1 & 0 \\ -2 & 1 \end{vmatrix}=2(0-4)+1(1+8)+3(1-0)=-8+9+3=4$ . Pitfall: the minus sign in front of the second term, which turns $-(-1)$ into $+1$ ; forgetting it gives $-14$ .

Check: a product is cross-checked by recomputing another entry the other way, row against column. For the inverse, $GG^{-1}$ must give back the identity: row 1 of $G$ against column 2 of $G^{-1}$ gives $4\left(-\frac{3}{2}\right)+3(2)=0$ . For a $3\times 3$ determinant, redo the computation along another row or with the rule of Sarrus.

Tick the exercises you have done or want to review: a free account, no password, keeps your ticks and your right answers from one visit to the next, tells you which chapter to tackle next and lets you ask for the exercise you are missing. Create your space, an email is enough.

Exercise 1: Graph vocabulary: vertices, edges, degrees

An undirected graph $G$ consists of a set $V(G)$ of vertices and a set $E(G)$ of edges, each edge being a pair of vertices. The degree of a vertex is the number of edges that end at it. The graph below has five vertices; note that its vertex $E$ is not the edge set $E(G)$ .

a) List the elements of $V(G)$ and $E(G)$ . How many edges are there?
b) Give the degree of each vertex.
c) Check the handshaking lemma: the sum of the degrees equals twice the number of edges.
d) Explain why this lemma holds for every graph, and deduce that the number of vertices of odd degree is even.
e) What is the maximum number of edges of a simple graph with 5 vertices? And with $n$ vertices?
f) Is there a path from $A$ to $E$ ? Is the graph connected?

Type your answers, the page tells you right or wrong 0/15

a)

Number of vertices

Number of edges

b)

\deg(A)

\deg(B)

\deg(C)

\deg(D)

\deg(E)

c)

Sum of the degrees

Twice the number of edges

d)

Each edge contributes to the sum of the degrees

Vertices of odd degree

e)

Maximum number of edges on 5 vertices

On

n

vertices, the maximum is

f)

The graph is

Minimum number of edges of a connected graph on 5 vertices

Show the solution

Answers

a) $V(G) = \{A,B,C,D,E\}$ and $E(G) = \{AB, AC, BC, BD, CD, DE\}$ , that is, 6 edges
b) $2, 3, 3, 3, 1$
c) $2+3+3+3+1 = 12 = 2 \times 6$
d) Each edge counts 2 in the sum, which is therefore even: the vertices of odd degree come in an even number, four here
e) $\dbinom{5}{2} = 10$ , and $\dfrac{n(n-1)}{2}$ in general
f) Yes, $A \to B \to D \to E$ : the graph is connected

a)

$V(G) = \{A, B, C, D, E\}$ and $E(G) = \{AB, AC, BC, BD, CD, DE\}$ , that is, 6 edges. Read them off by sweeping the drawing in a fixed order, for example alphabetically on the first vertex, so as to forget none and count none twice.

b)

$\deg(A) = 2$ (to $B$ and $C$ ), $\deg(B) = 3$ (to $A$ , $C$ , $D$ ), $\deg(C) = 3$ (to $A$ , $B$ , $D$ ), $\deg(D) = 3$ (to $B$ , $C$ , $E$ ), $\deg(E) = 1$ (to $D$ ).

c)

Sum of the degrees: $2+3+3+3+1 = 12$ . Number of edges: 6. We do have $12 = 2 \times 6$ . This check is the first one to make after reading off a graph: if it fails, an edge has been forgotten or counted twice.

d)

Each edge has two endpoints, so it contributes 1 to the degree of each of them, that is, 2 to the total of the degrees. Summing over all the edges gives $\sum_{v} \deg(v) = 2\lvert E(G) \rvert$ . This sum is even; the vertices of even degree contribute an even amount to it, so the contribution of the vertices of odd degree must also be even, which is only possible if there is an even number of them. Here, the vertices of odd degree are $B$ , $C$ , $D$ and $E$ : there are indeed four of them.

e)

In a simple graph, there is at most one edge per pair of vertices and no loop: the maximum is the number of pairs, $\dbinom{5}{2} = \dfrac{5 \times 4}{2} = 10$ edges, and $\dfrac{n(n-1)}{2}$ in general. Such a graph is called complete. Our graph has 6 of the 10 possible edges.

f)

Yes: $A \to B \to D \to E$ is a path, and there are others, such as $A \to C \to D \to E$ . The graph is connected, since step by step every vertex is reached from $A$ : $B$ and $C$ directly, $D$ through $B$ , $E$ through $D$ . A connected graph with $n$ vertices has at least $n-1$ edges; here $6 \ge 4$ , which is consistent, without being a proof on its own.

Exercise 2: Adjacency matrix of a directed graph

The adjacency matrix $M$ of a graph with $n$ vertices is the $n \times n$ matrix whose entry $M_{ij}$ is 1 if there is an arc from vertex $i$ to vertex $j$ , and 0 otherwise. It holds exactly the same information as the drawing, but it can be computed with. The directed graph below has four vertices numbered 1 to 4.

a) Read off the six arcs, then write the adjacency matrix $M$ .
b) What does the sum of the entries of a row represent? And of a column?
c) Give the out-degree and the in-degree of each vertex, then check that the two sums are equal.
d) The adjacency matrix of an undirected graph has a particular property: which one, and why?
e) What would a nonzero entry on the diagonal mean?

Type your answers, the page tells you right or wrong 0/14

a)

Entries equal to 1

M_{13}

M_{31}

M_{21}

M_{43}

b)

The sum of a ROW is

The sum of a COLUMN is

c)

Sum of the out-degrees

Sum of the in-degrees

In-degree of vertex 3

d)

It is

Our matrix

e)

A 1 on the diagonal would signal

Loops in this graph

Show the solution

Answers

a) Six arcs, $1\to2$ , $1\to3$ , $2\to3$ , $2\to4$ , $3\to1$ , $4\to3$ , and 6 entries equal to 1
b) Row: OUT-degree. Column: IN-degree
c) Out-degrees $2,2,1,1$ and in-degrees $1,1,3,1$ : both sums equal 6, the number of arcs
d) It is SYMMETRIC. Ours is not: $M_{12}=1$ and $M_{21}=0$
e) A LOOP. Our diagonal is zero

a)

The arcs are $1 \to 2$ , $1 \to 3$ , $2 \to 3$ , $2 \to 4$ , $3 \to 1$ and $4 \to 3$ . Listing the vertices in the order 1, 2, 3, 4, row $i$ describes the arcs THAT LEAVE $i$ : $M = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix}$ . Check: the matrix has 6 entries equal to 1, as many as the graph has arcs.

b)

The sum of row $i$ is the number of arcs leaving $i$ , that is, its OUT-degree. The sum of column $j$ is the number of arcs arriving at $j$ , its IN-degree. Confusing the two is the mistake that skews the whole rest of the chapter, because it amounts to transposing the graph.

c)

Out-degrees: $2, 2, 1, 1$ , with sum 6. In-degrees: vertex 1 receives from 3, so 1; vertex 2 receives from 1, so 1; vertex 3 receives from 1, 2 and 4, so 3; vertex 4 receives from 2, so 1. Sum: $1+1+3+1 = 6$ . Both sums equal 6, the number of arcs: each arc has exactly one tail and one head. This is the directed version of the handshaking lemma, without the factor 2.

d)

It is SYMMETRIC, that is, equal to its transpose. An undirected edge between $i$ and $j$ can be read in both directions, so $M_{ij} = M_{ji}$ . Conversely, a symmetric adjacency matrix describes a graph that can be regarded as undirected. Our matrix is not symmetric: $M_{12} = 1$ but $M_{21} = 0$ , which confirms that the graph is indeed directed.

e)

An entry $M_{ii} = 1$ would signal a LOOP, that is, an arc from a vertex to itself. Our graph has none, its diagonal is zero. Loops are forbidden in a so-called simple graph, but they appear naturally as soon as you model an automaton or a web page that links to itself.

Exercise 3: Matrix operations and noncommutativity

Let $A = \begin{pmatrix} 1 & 2 \\ 3 & -1 \end{pmatrix}$ and $B = \begin{pmatrix} 0 & 4 \\ 2 & 1 \end{pmatrix}$ . Entry $(i,j)$ of the product $AB$ is obtained by running row $i$ of $A$ against column $j$ of $B$ : it is the only rule of the chapter, and on its own it explains why the product is not commutative.

a) Compute $A + B$ and $2A - 3B$ .
b) Compute $AB$ and $BA$ . What do you observe?
c) Give $A^{T}$ and $B^{T}$ .
d) Check on this example that $(AB)^{T} = B^{T}A^{T}$ .
e) Under what condition on the sizes does the product $PQ$ exist?
f) Compute $A^{2}$ . Is it the matrix of the squares of the entries of $A$ ?

Type your answers, the page tells you right or wrong 0/18

a)

(A+B)_{12}

(A+B)_{21}

(2A-3B)_{12}

(2A-3B)_{22}

b)

(AB)_{11}

(AB)_{22}

(BA)_{11}

(BA)_{12}

You observe that

c)

(A^{T})_{12}

(B^{T})_{12}

d)

\big((AB)^{T}\big)_{12}

(B^{T}A^{T})_{21}

The transpose of a product is

e)

The product

PQ

exists if and only if

f)

(A^{2})_{11}

(A^{2})_{12}

Is it the matrix of the squares of the entries?

Show the solution

Answers

a) $A+B = \begin{pmatrix} 1 & 6 \\ 5 & 0 \end{pmatrix}$ and $2A-3B = \begin{pmatrix} 2 & -8 \\ 0 & -5 \end{pmatrix}$
b) $AB = \begin{pmatrix} 4 & 6 \\ -2 & 11 \end{pmatrix}$ and $BA = \begin{pmatrix} 12 & -4 \\ 5 & 3 \end{pmatrix}$ : the product is not commutative
c) $A^{T} = \begin{pmatrix} 1 & 3 \\ 2 & -1 \end{pmatrix}$ and $B^{T} = \begin{pmatrix} 0 & 2 \\ 4 & 1 \end{pmatrix}$
d) Both equal $\begin{pmatrix} 4 & -2 \\ 6 & 11 \end{pmatrix}$ : the order is REVERSED
e) Columns of $P$ = rows of $Q$ , and the product is of size $m \times p$
f) $A^{2} = 7I$ , not the matrix of the squares: $A$ is invertible, with inverse $\dfrac{1}{7}A$

a)

$A+B = \begin{pmatrix} 1 & 6 \\ 5 & 0 \end{pmatrix}$ , term by term. For the combination: $2A = \begin{pmatrix} 2 & 4 \\ 6 & -2 \end{pmatrix}$ and $3B = \begin{pmatrix} 0 & 12 \\ 6 & 3 \end{pmatrix}$ , so $2A - 3B = \begin{pmatrix} 2 & -8 \\ 0 & -5 \end{pmatrix}$ .

b)

$AB = \begin{pmatrix} 1(0)+2(2) & 1(4)+2(1) \\ 3(0)+(-1)(2) & 3(4)+(-1)(1) \end{pmatrix} = \begin{pmatrix} 4 & 6 \\ -2 & 11 \end{pmatrix}$ . And $BA = \begin{pmatrix} 0(1)+4(3) & 0(2)+4(-1) \\ 2(1)+1(3) & 2(2)+1(-1) \end{pmatrix} = \begin{pmatrix} 12 & -4 \\ 5 & 3 \end{pmatrix}$ . The two products differ: the matrix product is NOT commutative. It is the most important difference from the product of real numbers, and in computer graphics it has a concrete meaning: rotating then translating does not give the same image as translating then rotating.

c)

$A^{T} = \begin{pmatrix} 1 & 3 \\ 2 & -1 \end{pmatrix}$ and $B^{T} = \begin{pmatrix} 0 & 2 \\ 4 & 1 \end{pmatrix}$ : the first row becomes the first column.

d)

$(AB)^{T} = \begin{pmatrix} 4 & -2 \\ 6 & 11 \end{pmatrix}$ . And $B^{T}A^{T} = \begin{pmatrix} 0(1)+2(2) & 0(3)+2(-1) \\ 4(1)+1(2) & 4(3)+1(-1) \end{pmatrix} = \begin{pmatrix} 4 & -2 \\ 6 & 11 \end{pmatrix}$ . The two coincide. The point to remember is the REVERSAL of the order: the transpose of a product is the product of the transposes taken in reverse order. The same reversal happens for the inverse of a product.

e)

The product $PQ$ exists if and only if the number of COLUMNS of $P$ equals the number of ROWS of $Q$ . If $P$ is of size $m \times n$ and $Q$ of size $n \times p$ , then $PQ$ is of size $m \times p$ . This is the check to make before any computation: quite often, $AB$ exists and $BA$ does not, which settles the question of commutativity without the slightest computation.

f)

$A^{2} = AA = \begin{pmatrix} 1(1)+2(3) & 1(2)+2(-1) \\ 3(1)+(-1)(3) & 3(2)+(-1)(-1) \end{pmatrix} = \begin{pmatrix} 7 & 0 \\ 0 & 7 \end{pmatrix}$ . It is clearly not the matrix of the squares, which would be $\begin{pmatrix} 1 & 4 \\ 9 & 1 \end{pmatrix}$ . The result is remarkable here: $A^{2} = 7I$ , so $A$ behaves like a square root of 7 times the identity. It follows at once that $A$ is invertible, with inverse $\dfrac{1}{7}A$ .

Exercise 4: Powers of the adjacency matrix and counting paths

We return to the matrix $M$ of the directed graph of exercise 2. The central theorem of the chapter: entry $(i,j)$ of $M^{k}$ is the NUMBER of paths of length exactly $k$ from $i$ to $j$ . A path is allowed to pass again through a vertex it has already visited (some textbooks call such a path a walk, and keep the word path for a simple path).

The graph of exercise 2 is shown again below.

a) Compute $M^{2}$ .
b) Interpret entry $(1,1)$ of $M^{2}$ by exhibiting the corresponding path.
c) Compute $M^{3}$ and read off the number of paths of length 3 from 1 to 3. Write them all out.
d) Prove the theorem in the case $k=2$ .
e) How many paths of length 2 leave vertex 1, all destinations together?

Type your answers, the page tells you right or wrong 0/13

a)

(M^{2})_{11}

(M^{2})_{14}

(M^{2})_{32}

(M^{2})_{41}

b)

Value of the entry

The corresponding path is

The diagonal entries of

M^{k}

count

c)

(M^{3})_{13}

The second path is

d)

The term

M_{ik}M_{kj}

is 1 exactly when

The general case follows

e)

Paths of length 2 leaving 1

Check by successors

Show the solution

Answers

a) $M^{2} = \begin{pmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix}$
b) It is 1: the only cycle $1 \to 3 \to 1$ of length 2
c) $(M^{3})_{13} = 2$ : $1 \to 2 \to 4 \to 3$ and $1 \to 3 \to 1 \to 3$
d) $(M^{2})_{ij} = \sum_{k} M_{ik}M_{kj}$ , each term being 1 for a path $i \to k \to j$
e) $1+0+1+1 = 3$ , confirmed by the count through successors $2+1 = 3$

a)

Multiply $M$ by itself. Row 1: vertex 1 points to 2 and 3, so row 1 of $M^{2}$ is the sum of rows 2 and 3 of $M$ , that is, $(0,0,1,1) + (1,0,0,0) = (1,0,1,1)$ . Row 2: vertex 2 points to 3 and 4, sum of rows 3 and 4: $(1,0,0,0)+(0,0,1,0) = (1,0,1,0)$ . Row 3: vertex 3 points to 1, so row 1 of $M$ : $(0,1,1,0)$ . Row 4: vertex 4 points to 3, so row 3 of $M$ : $(1,0,0,0)$ . Hence $M^{2} = \begin{pmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix}$ . This method, where each row of the product is a sum of rows, is much faster than computing entry by entry when the matrix contains only 0s and 1s.

b)

Entry $(1,1)$ of $M^{2}$ is 1: there is exactly one path of length 2 from vertex 1 to itself, namely $1 \to 3 \to 1$ . It is a cycle of length 2, and it shows up on the diagonal: the diagonal entries of $M^{k}$ count the closed paths of length $k$ through each vertex.

c)

$M^{3} = M^{2}M$ . Row 1: $(1,0,1,1)$ picks out rows 1, 3 and 4 of $M$ , whose sum is $(0,1,1,0)+(1,0,0,0)+(0,0,1,0) = (1,1,2,0)$ . Continuing: $M^{3} = \begin{pmatrix} 1 & 1 & 2 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}$ . Entry $(1,3)$ is 2: there are two paths of length 3 from 1 to 3, namely $1 \to 2 \to 4 \to 3$ and $1 \to 3 \to 1 \to 3$ . The second one passes again through vertices already seen, which is allowed: that is precisely why the entry is 2 and not 1. Confusing a path with a simple path is the mistake that makes students miss this theorem.

d)

By definition of the product, $(M^{2})_{ij} = \sum_{k} M_{ik}M_{kj}$ . Each term of this sum is 1 exactly when $M_{ik} = 1$ AND $M_{kj} = 1$ , that is, when there is an arc from $i$ to $k$ AND an arc from $k$ to $j$ : this describes precisely a path $i \to k \to j$ of length 2 through $k$ . The sum over $k$ therefore counts all the paths of length 2 from $i$ to $j$ , one for each possible intermediate vertex. The general case follows by induction, writing $M^{k+1} = M^{k}M$ and splitting each path of length $k+1$ into a path of length $k$ followed by an arc.

e)

It is the sum of the first row of $M^{2}$ : $1+0+1+1 = 3$ . Another reading: vertex 1 has two successors, 2 and 3, which have 2 and 1 successors respectively, giving $2+1 = 3$ paths. The two counts agree, which validates the matrix computation.

Exercise 5: Connectivity and the reachability matrix

Knowing whether a path exists, regardless of its length, amounts to combining all the powers of the adjacency matrix while replacing addition by a logical OR. The resulting matrix is called the reachability matrix, or transitive closure: its entry $(i,j)$ is 1 as soon as some path leads from $i$ to $j$ .

The graph of exercise 2 is shown again below.

a) Up to which power of $M$ must you go in a graph with $n$ vertices?
b) Determine the reachability matrix of the directed graph of exercise 2.
c) Is this graph strongly connected?
d) The undirected graph of exercise 1 is connected. How many edges must be removed to obtain a spanning tree, and how many will remain?
e) What is the cost in operations of Warshall's algorithm on $n$ vertices?

Type your answers, the page tells you right or wrong 0/11

a)

You must go up to

b)

Entries equal to 1 in the reachability matrix

Entries equal to 1 when stopping at

M^{3}

The last cell to be filled is

c)

The graph is

The cycle that proves it is

d)

Edges of a spanning tree

Edges to remove

This number is called

e)

The cost of Warshall is

Computing and then combining the powers would cost

Show the solution

Answers

a) Up to $M^{n}$ : a return to a vertex itself may need $n$ arcs
b) Filled entirely with 1s; at $M^{3}$ cell $(4,4)$ was still missing
c) Yes, strongly connected: the cycle $4 \to 3 \to 1 \to 2 \to 4$ passes through all four vertices
d) A spanning tree has $5-1 = 4$ edges: 2 must be removed, the cyclomatic number
e) Warshall costs $n^{3}$ , against $n^{4}$ for combining the powers

a)

A path that passes twice through the same vertex contains a cycle that can be deleted without changing its endpoints. For $i \neq j$ , if there is a path from $i$ to $j$ , there is therefore one without repetition: it visits at most $n$ vertices and has at most $n-1$ arcs. For a return from $i$ to itself, on the other hand, the cycle may visit all $n$ vertices and then have $n$ arcs. You must therefore go up to $M^{n}$ , and $M^{n-1}$ is enough only if you restrict yourself to pairs of distinct vertices. The next question shows that this distinction is not just theoretical.

b)

Combine $M$ , $M^{2}$ , $M^{3}$ and $M^{4}$ , putting a 1 wherever any one of the four has one. $M$ gives the pairs $(1,2), (1,3), (2,3), (2,4), (3,1), (4,3)$ ; $M^{2}$ adds $(1,1), (1,4), (2,1), (3,2), (3,3), (4,1)$ ; $M^{3}$ adds $(2,2), (3,4), (4,2)$ . At this stage, a single position is still 0, position $(4,4)$ : fifteen cells out of sixteen are filled. It is filled by $M^{4}$ , thanks to the cycle $4 \to 3 \to 1 \to 2 \to 4$ , which has four arcs. The reachability matrix is therefore filled entirely with 1s. This is the exact illustration of question a): this cycle passes through all four vertices, so it needs four arcs, and stopping at $M^{3}$ would have concluded, wrongly, that vertex 4 cannot return to itself.

c)

Yes. A directed graph is strongly connected when every vertex is reachable from every other one, which is read exactly on a reachability matrix filled entirely with 1s. The cycle $4 \to 3 \to 1 \to 2 \to 4$ is in fact enough to convince yourself without a matrix: it passes through all four vertices, so by following it long enough you go from any vertex to any other.

d)

A spanning tree of a connected graph with $n$ vertices has exactly $n-1$ edges, here $5-1 = 4$ . The graph has 6, so $6-4 = 2$ must be removed, taking care not to break any connection. For example, removing $BC$ and $CD$ leaves $AB$ , $AC$ , $BD$ , $DE$ , which do link the five vertices without a cycle. The number of edges to remove, $\lvert E(G) \rvert - \lvert V(G) \rvert + 1$ , is called the cyclomatic number and counts the independent cycles of the graph.

e)

Warshall's algorithm consists of three nested loops over the vertices, each of length $n$ : its cost is of the order of $n^{3}$ operations. That is cheaper than computing and combining the first $n$ powers of $M$ , which would cost about $n$ matrix multiplications at $n^{3}$ operations each, that is, $n^{4}$ . The difference rests on a single idea: Warshall updates the matrix IN PLACE, allowing the intermediate vertices one at a time.

Exercise 6: Plane transformations: matrices and computer graphics

In computer graphics, a point of the plane is a column vector $\begin{pmatrix} x \\ y \end{pmatrix}$ , and a linear transformation is a $2 \times 2$ matrix that multiplies it. Here three transformations are applied to the triangle $T$ with vertices $P_{1}(1,1)$ , $P_{2}(4,1)$ and $P_{3}(1,3)$ .

a) Write the matrix $H$ of the dilation with factor 2 centred at the origin, and give the image of $T$ .
b) Write the matrix $R$ of the rotation through $90$ degrees about the origin, and give the image of $T$ .
c) Write the matrix $S$ of the reflection across the x-axis.
d) Compute the area of $T$ , then that of $H(T)$ and of $R(T)$ .
e) What link do you see between the determinant of a matrix and the effect of the transformation on areas?
f) Can a translation by the vector $(3,1)$ be written as a $2 \times 2$ matrix?

Type your answers, the page tells you right or wrong 0/17

a)

H_{11}

Image of

P_{2}(4,1)

b)

The columns of

R

are

Image of

P_{1}(1,1)

The columns of a matrix are

c)

S_{11}

S_{22}

d)

Area of

T

Area of

H(T)

Area of

R(T)

e)

\det H

\det R

\det S

Area is multiplied by

A zero determinant means that the transformation

f)

A translation

The problem is solved by

Show the solution

Answers

a) $H = 2I$ , and $T$ becomes $(2,2)$ , $(8,2)$ , $(2,6)$
b) $R = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$ , and $T$ becomes $(-1,1)$ , $(-1,4)$ , $(-3,1)$
c) $S = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$
d) Area of $T$ : 3; of $H(T)$ : 12; of $R(T)$ : 3
e) Area is multiplied by $\lvert \det \rvert$ : 4 for $H$ , 1 for $R$ , 1 for $S$ with the orientation reversed
f) No: a linear transformation fixes the origin. Homogeneous coordinates are needed

a)

$H = \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix} = 2I$ . The images are $H(P_{1}) = (2,2)$ , $H(P_{2}) = (8,2)$ and $H(P_{3}) = (2,6)$ : each coordinate is doubled. A dilation with factor $k$ centred at the origin is always $kI$ , and these scalar matrices are the only ones that commute with all the others.

b)

The rotation through $90$ degrees sends $(1,0)$ to $(0,1)$ and $(0,1)$ to $(-1,0)$ . These images are the columns of the matrix, hence $R = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$ , that is, $(x,y) \mapsto (-y,x)$ . Images: $R(P_{1}) = (-1,1)$ , $R(P_{2}) = (-1,4)$ and $R(P_{3}) = (-3,1)$ . The general rule is worth remembering: the columns of a matrix are the images of the basis vectors.

c)

The reflection across the x-axis leaves $x$ unchanged and changes the sign of $y$ : $S = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$ . It is the transformation implicitly undergone by every image displayed on a screen, where the vertical axis points down.

d)

$T$ has a right angle at $P_{1}$ , with legs $P_{1}P_{2} = 3$ and $P_{1}P_{3} = 2$ : its area is $\dfrac{3 \times 2}{2} = 3$ . After the dilation, both legs double and the area is multiplied by 4: it is 12. After the rotation, the figure is congruent to the original one: the area stays 3.

e)

Area is multiplied by $\lvert \det \rvert$ . Indeed $\det H = 4$ and the area was multiplied by 4; $\det R = 0 \times 0 - (-1)(1) = 1$ and the area is preserved; $\det S = -1$ , the area is preserved but the orientation is reversed, which the negative sign signals. A matrix with determinant zero squashes the figure onto a line or a point: the area becomes zero, and the transformation cannot be reversed.

f)

No. A linear transformation always fixes the origin, since $M \begin{pmatrix} 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}$ , whereas a translation moves the origin to $(3,1)$ . No $2 \times 2$ matrix can therefore translate. That is precisely the problem that homogeneous coordinates solve, by adding a third coordinate equal to 1 and working with $3 \times 3$ matrices.

Exercise 7: Determinant, inverse matrix and reversibility

A square matrix is invertible exactly when its determinant is nonzero, and the inverse undoes what the matrix did. For a $2 \times 2$ matrix, $\begin{pmatrix} a & b \\ c & d \end{pmatrix}^{-1} = \dfrac{1}{ad-bc}\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}$ : swap the diagonal entries, change the sign of the off-diagonal entries, divide by the determinant.

a) Compute $\det A$ for $A = \begin{pmatrix} 1 & 2 \\ 3 & -1 \end{pmatrix}$ , then $A^{-1}$ .
b) Check that $AA^{-1} = I$ .
c) Compute the determinant of $N = \begin{pmatrix} 2 & 1 & 0 \\ 1 & 3 & 1 \\ 0 & 1 & 2 \end{pmatrix}$ by cofactor expansion along the first row.
d) Give the inverse of the rotation matrix $R$ of the previous exercise, and interpret it.
e) Is the matrix $\begin{pmatrix} 2 & 4 \\ 1 & 2 \end{pmatrix}$ invertible? What does it do geometrically?
f) Why is $(PQ)^{-1} = Q^{-1}P^{-1}$ and not $P^{-1}Q^{-1}$ ?

Type your answers, the page tells you right or wrong 0/13

a)

\det A

A^{-1}

is

b)

(AA^{-1})_{11}

(AA^{-1})_{12}

c)

First minor

Second minor

\det N

d)

R^{-1}

is

Note also that

e)

Its determinant

Geometrically, it

f)

The operations must be undone

The check is

Show the solution

Answers

a) $\det A = -7$ and $A^{-1} = \dfrac{1}{7}A = \begin{pmatrix} 1/7 & 2/7 \\ 3/7 & -1/7 \end{pmatrix}$
b) $AA^{-1} = \dfrac{1}{7}(7I) = I$
c) $\det N = 2(5) - 1(2) + 0 = 8$
d) $R^{-1} = \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}$ , the rotation through $-90$ degrees, and $R^{-1} = R^{T}$
e) No, its determinant is zero: it squashes the plane onto the line spanned by $(2,1)$
f) Because you undo in reverse order: $(PQ)(Q^{-1}P^{-1}) = I$

a)

$\det A = (1)(-1) - (2)(3) = -1 - 6 = -7$ , nonzero, so $A$ is invertible. The formula gives $A^{-1} = \dfrac{1}{-7}\begin{pmatrix} -1 & -2 \\ -3 & 1 \end{pmatrix} = \begin{pmatrix} 1/7 & 2/7 \\ 3/7 & -1/7 \end{pmatrix}$ . This matches the result of exercise 3: since $A^{2} = 7I$ , we do have $A^{-1} = \dfrac{1}{7}A$ .

b)

$AA^{-1} = \dfrac{1}{7}A^{2} = \dfrac{1}{7}(7I) = I$ . In detail: entry $(1,1)$ is $1(1/7) + 2(3/7) = 1/7 + 6/7 = 1$ ; entry $(1,2)$ is $1(2/7) + 2(-1/7) = 0$ . The check by the product is mandatory, because a sign error in the inverse formula cannot be seen any other way.

c)

Expand along the first row: $\det N = 2\begin{vmatrix} 3 & 1 \\ 1 & 2 \end{vmatrix} - 1\begin{vmatrix} 1 & 1 \\ 0 & 2 \end{vmatrix} + 0 = 2(6-1) - 1(2-0) + 0 = 10 - 2 = 8$ . The third term is zero because its coefficient is: choosing the row or column with the most zeros saves a whole minor, and here the first row as well as the third contains a zero.

d)

$\det R = 1$ , and the formula gives $R^{-1} = \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}$ . It is the matrix of the rotation through $-90$ degrees: undoing a rotation means turning the other way. Note also that $R^{-1} = R^{T}$ , which holds for every rotation matrix and makes inversion free in a graphics engine.

e)

$\det = (2)(2) - (4)(1) = 0$ : it is not invertible. Geometrically, it squashes the whole plane onto a line: the two columns $(2,1)$ and $(4,2)$ are proportional, so all the images are multiples of $(2,1)$ . Information is lost, several different points have the same image, and no matrix can undo that. That is exactly what a zero determinant expresses: area is squashed to zero.

f)

Because the operations must be undone in the reverse of the order in which they were done. Check: $(PQ)(Q^{-1}P^{-1}) = P(QQ^{-1})P^{-1} = PIP^{-1} = PP^{-1} = I$ . The same reversal appears for the transpose, $(PQ)^{T} = Q^{T}P^{T}$ . A concrete picture: to undo “put on your socks, then your shoes”, you take off the shoes first.

Exercise 8: Five statements to correct

Each of the following five statements is FALSE. Say why and give the correct statement.

1) “The product of two matrices is commutative: $PQ = QP$ .”
2) “The sum of the degrees of a graph equals its number of edges.”
3) “If $\det(P) = 0$ , then $P$ has an inverse matrix.”
4) “The adjacency matrix of a directed graph is always symmetric.”
5) “Entry $(i,j)$ of $M^{2}$ gives the number of edges between $i$ and $j$ .”

Type your answers, the page tells you right or wrong 0/10

1)

The matrix product is

(AB)_{11}

(BA)_{11}

2)

Sum of the degrees of the graph of exercise 1

Its number of edges

3)

A matrix is invertible if and only if its determinant is

4)

Symmetry characterizes

5)

(M^{k})_{ij}

gives

(M^{2})_{11}

for the graph of exercise 2

Loops at vertex 1

Show the solution

Answers

1) FALSE: $AB \neq BA$ , and sometimes $BA$ does not even exist
2) FALSE: $\sum_{v} \deg(v) = 2\lvert E \rvert$ , that is, 12 for 6 edges
3) FALSE: it is the opposite, $P$ is invertible if and only if $\det(P) \neq 0$
4) FALSE: symmetry characterizes UNDIRECTED graphs
5) FALSE: $(M^{k})_{ij}$ counts the PATHS of length $k$ , repetitions allowed

1)

FALSE. Counterexample from exercise 3: $AB = \begin{pmatrix} 4 & 6 \\ -2 & 11 \end{pmatrix}$ whereas $BA = \begin{pmatrix} 12 & -4 \\ 5 & 3 \end{pmatrix}$ . It even happens that $PQ$ exists and $QP$ does not, if the sizes only fit together one way. Correct statement: the matrix product is associative and distributive, but not commutative; only a few special families commute, such as the multiples of the identity.

2)

FALSE. Each edge counts 1 in the degree of each of its TWO endpoints. Counterexample: the graph of exercise 1 has 6 edges and a sum of degrees equal to 12. Correct statement: $\sum_{v} \deg(v) = 2\lvert E \rvert$ , the handshaking lemma.

3)

FALSE. It is exactly the opposite: a matrix is invertible if and only if its determinant is NONZERO. Counterexample: $\begin{pmatrix} 2 & 4 \\ 1 & 2 \end{pmatrix}$ has determinant zero and squashes the plane onto a line, so several points have the same image and no transformation can tell them apart. Correct statement: $P$ is invertible if and only if $\det(P) \neq 0$ .

4)

FALSE. Symmetry characterizes UNDIRECTED graphs, where an edge can be travelled in both directions. Counterexample: in the graph of exercise 2, $M_{12} = 1$ and $M_{21} = 0$ , because the arc goes from 1 to 2 and not the other way. Correct statement: the adjacency matrix is symmetric if and only if the graph is undirected.

5)

FALSE. The number of edges from $i$ to $j$ is read in $M$ itself, not in its square. Counterexample: in the graph of exercise 2, $(M^{2})_{11} = 1$ although there is no loop at vertex 1. Correct statement: $(M^{k})_{ij}$ is the number of PATHS of length exactly $k$ from $i$ to $j$ , repeated vertices being allowed.

Exercise 9: Problem: a cable network and its distance matrix

Five data centres $A$ , $B$ , $C$ , $D$ and $E$ are joined by links whose length, in kilometres, is shown on the diagram. A missing link means that there is no direct cable between the two centres.

a) Give the degree of each vertex and check the handshaking lemma.
b) Write the weight matrix $W$ , putting 0 on the diagonal and a dash where there is no link.
c) Give all the routes from $A$ to $E$ that do not pass twice through the same centre, with their length.
d) What is the shortest route from $A$ to $E$ ?
e) Is the shortest route the one with the fewest links?
f) If link $DE$ fails, does the network stay connected? What becomes the shortest route from $A$ to $E$ ?

Type your answers, the page tells you right or wrong 0/19

a)

\deg(C)

Sum of the degrees

Number of links

b)

Weight of

AC

Weight of

BC

Weight of

CE

The matrix is

c)

A \to C \to E

km

A \to C \to D \to E

km

A \to B \to D \to E

km

A \to C \to B \to D \to E

km

d)

Length of the shortest route km

This route is

e)

Links in the shortest route

Links in

A \to C \to E

Minimizing the number of edges and minimizing the weight

f)

The network

New minimum length km

Cost of the failure km

Show the solution

Answers

a) $2, 3, 4, 3, 2$ , with sum $14 = 2 \times 7$
b) Symmetric matrix, zero diagonal, a dash for $AD$ , $AE$ and $BE$
c) $A\to C\to E$ : 12; $A\to C\to D\to E$ : 12; $A\to B\to D\to E$ : 11; $A\to C\to B\to D\to E$ : 10; $A\to B\to C\to D\to E$ : 15; $A\to B\to C\to E$ : 15; $A\to B\to D\to C\to E$ : 27
d) $A \to C \to B \to D \to E$ , 10 km
e) No: it has FOUR links, against two for $A \to C \to E$ , which is 12 km
f) Yes, $E$ keeps its link to $C$ . The shortest becomes $A \to C \to E$ , 12 km, that is, 2 km more

a)

$\deg(A) = 2$ (to $B$ and $C$ ), $\deg(B) = 3$ (to $A$ , $C$ , $D$ ), $\deg(C) = 4$ (to $A$ , $B$ , $D$ , $E$ ), $\deg(D) = 3$ (to $B$ , $C$ , $E$ ), $\deg(E) = 2$ (to $C$ , $D$ ). Sum: $2+3+4+3+2 = 14$ , and the network has 7 links: $14 = 2 \times 7$ . The lemma checks out, so no link was forgotten when reading off the diagram.

b)

Listing the centres in the order $A, B, C, D, E$ : the row of $A$ is $0, 4, 2, -, -$ ; that of $B$ is $4, 0, 1, 5, -$ ; that of $C$ is $2, 1, 0, 8, 10$ ; that of $D$ is $-, 5, 8, 0, 2$ ; that of $E$ is $-, -, 10, 2, 0$ . The matrix is symmetric, since the links are not directed. In a program, the dash is coded by a very large value, so that any route using it is automatically discarded when the minimum is computed.

c)

There are seven routes without repetition. Four of them are short. $A \to C \to E$ : $2+10 = 12$ . $A \to C \to D \to E$ : $2+8+2 = 12$ . $A \to B \to D \to E$ : $4+5+2 = 11$ . $A \to C \to B \to D \to E$ : $2+1+5+2 = 10$ . The other three are longer: $A \to B \to C \to D \to E$ : $4+1+8+2 = 15$ , $A \to B \to C \to E$ : $4+1+10 = 15$ , and $A \to B \to D \to C \to E$ : $4+5+8+10 = 27$ . The enumeration is done as a tree, fixing the first step and then the second, which guarantees that no route is forgotten: four routes start with $A \to B$ and three with $A \to C$ .

d)

The shortest is $A \to C \to B \to D \to E$ , with 10 kilometres. It narrowly beats $A \to B \to D \to E$ , which is 11.

e)

No, and that is the whole point of the example. The shortest route has FOUR links, whereas $A \to C \to E$ has only two, for 12 kilometres. Making a detour through $C$ then $B$ costs one more link but avoids the 10-kilometre cable. Minimizing the number of edges and minimizing the total weight are two different problems: the first is solved by a breadth-first search, the second requires an algorithm such as Dijkstra's.

f)

The network stays connected: $E$ keeps its link to $C$ . The shortest route from $A$ to $E$ becomes $A \to C \to E$ , that is, 12 kilometres, since every route to $E$ shorter than that ended with the link from $D$ to $E$ . The cost of the failure is therefore 2 kilometres. Since vertex $E$ has degree 2, it would have to lose both of its links to be isolated: that is the elementary measure of a network's robustness, and it explains why centres of degree 1 are avoided.

Exercise 10: Problem: composing transformations in homogeneous coordinates

For a translation to become a matrix product, a third coordinate equal to 1 is added to the point: the point $(x,y)$ is written $\begin{pmatrix} x \\ y \\ 1 \end{pmatrix}$ and the transformations become $3 \times 3$ matrices. Let $T$ be the translation by the vector $(3,1)$ and $R$ the rotation through $90$ degrees about the origin, and follow the point $P(2,0)$ .

The figure below shows the situation.

a) Write the $3 \times 3$ matrices of $T$ and of $R$ .
b) Compute $TR$ , then the image of $P$ under this matrix. Describe the order of the operations applied to $P$ .
c) Compute $RT$ , then the image of $P$ . Compare with the previous question.
d) Give the matrix that brings the point back to its initial position after $TR$ .
e) Check your answer on the image point found in b).
f) Why does a graphics processor prefer to compose the matrices rather than apply the transformations one by one?

Type your answers, the page tells you right or wrong 0/13

a)

The last column of

T

carries

The last row is always

b)

Image of

P

The order of the operations is

c)

Image of

P

The comparison shows

d)

The required matrix is

Its entry (1,3)

Its entry (2,3)

e)

We get back

f)

Matrix-vector products per vertex, without composing

After composing

What guarantees an identical result is

Show the solution

Answers

a) $T$ carries $(3,1)$ in its last column, $R$ carries the rotation block in the upper left corner, and the last row is $(0,0,1)$
b) $TR = \begin{pmatrix} 0 & -1 & 3 \\ 1 & 0 & 1 \\ 0 & 0 & 1 \end{pmatrix}$ and the image is $(3,3)$ : $R$ acts first
c) $RT = \begin{pmatrix} 0 & -1 & -1 \\ 1 & 0 & 3 \\ 0 & 0 & 1 \end{pmatrix}$ and the image is $(-1,5)$ , not $(3,3)$
d) $(TR)^{-1} = R^{-1}T^{-1} = \begin{pmatrix} 0 & 1 & -1 \\ -1 & 0 & 3 \\ 0 & 0 & 1 \end{pmatrix}$
e) The image of $(3,3)$ is $(2,0)$ : we do get back $P$
f) Six products per vertex against a single one after composing: associativity guarantees the same result

a)

$T = \begin{pmatrix} 1 & 0 & 3 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix}$ : the last column carries the translation vector. $R = \begin{pmatrix} 0 & -1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}$ : the upper left $2 \times 2$ block is the rotation, the rest completes the identity. The last row is always $(0,0,1)$ , which guarantees that the third coordinate of the result stays 1.

b)

$TR = \begin{pmatrix} 0 & -1 & 3 \\ 1 & 0 & 1 \\ 0 & 0 & 1 \end{pmatrix}$ . Applied to $P = (2,0,1)$ : the first coordinate is $0(2) + (-1)(0) + 3(1) = 3$ , the second $1(2) + 0(0) + 1(1) = 3$ . The image is $(3,3)$ . The order is read from right to left: $R$ acts first, sending $(2,0)$ to $(0,2)$ , then $T$ adds $(3,1)$ and gives $(3,3)$ . The rightmost factor is applied FIRST, which is confusing until you tie it to the notation $T(R(P))$ .

c)

$RT = \begin{pmatrix} 0 & -1 & -1 \\ 1 & 0 & 3 \\ 0 & 0 & 1 \end{pmatrix}$ . Applied to $P$ : first coordinate $0(2) + (-1)(0) + (-1)(1) = -1$ , second $1(2) + 0(0) + 3(1) = 5$ . The image is $(-1,5)$ , and not $(3,3)$ . Direct check: $T$ first sends $(2,0)$ to $(5,1)$ , then $R$ sends $(5,1)$ to $(-1,5)$ . Translating then rotating is not rotating then translating, because the rotation also carries along the displacement already made. This is the noncommutativity of the matrix product, seen on an image.

d)

You must undo in reverse order: first cancel $T$ , then cancel $R$ . The required matrix is $(TR)^{-1} = R^{-1}T^{-1}$ , with $R^{-1}$ the rotation through $-90$ degrees and $T^{-1}$ the translation by $(-3,-1)$ . The product is $\begin{pmatrix} 0 & 1 & -1 \\ -1 & 0 & 3 \\ 0 & 0 & 1 \end{pmatrix}$ .

e)

Apply this matrix to $(3,3,1)$ : first coordinate $0(3) + 1(3) + (-1)(1) = 2$ , second $(-1)(3) + 0(3) + 3(1) = 0$ . We get back $P = (2,0)$ . The check is conclusive, and it is better to do it on a point than to recompute the product $(TR)(R^{-1}T^{-1})$ , which is longer and more exposed to sign errors.

f)

Because a scene contains hundreds of thousands of vertices and a transformation often consists of five or six chained steps. Applying the transformations one by one would cost six matrix-vector products PER vertex. By first composing the six matrices, which is done only once for the whole scene, a single product per vertex remains. The associativity of the matrix product guarantees that the result is identical, and the gain is a factor equal to the number of transformations: that is why a graphics engine handles a single matrix, called the model-view-projection matrix.

Corrected exercises: introduction to graphs and matrices (201-N11)

Course recap

Calculations: matrix computations

Exercise 0.1: Computing with matrices: ten direct calculations

Part A: the basics (/50)

Exercise 1: Graph vocabulary: vertices, edges, degrees

Exercise 2: Adjacency matrix of a directed graph

Exercise 3: Matrix operations and noncommutativity

Exercise 4: Powers of the adjacency matrix and counting paths

Exercise 5: Connectivity and the reachability matrix

Part B: problems and reasoning (/50)

Exercise 6: Plane transformations: matrices and computer graphics

Exercise 7: Determinant, inverse matrix and reversibility

Exercise 8: Five statements to correct

Exercise 9: Problem: a cable network and its distance matrix

Exercise 10: Problem: composing transformations in homogeneous coordinates

See also

Looking for a discrete mathematics tutor in Montreal?