Mathematics for Computer Science 201-N11 • CEGEP, Montreal

Revision sheet: graphs and matrices (201-N11)

This revision sheet covers graphs and matrices in Mathematics for Computer Science, 201-N11, the discrete mathematics course taken at CEGEP by students in computer science programs. Graphs and matrices are two ways of writing the same object, and this back-and-forth is what the test checks: a question asked about the drawing is often solved faster on the matrix, and the reverse is true as well.

This sheet gathers the readings that earn marks: what the diagonal says, what symmetry says, what exactly a power counts, and why the order of a product of transformations never leaves the result unchanged.

Mark this sheet as read or add it to your favourites: a free account, no password, keeps your read sheets and favourites from one visit to the next, tells you which chapter to tackle next and lets you ask for the method or exercise you are missing. Create your space, an email is enough.

The thread of the chapter

An adjacency matrix is not a table of numbers: each entry is an arc, and the $k$ -th power counts the paths of length EXACTLY $k$ .

This chapter is part of 201-N11, Mathematics for Computer Science

The essentials

Degrees, edges and the handshaking lemma

• $\sum_{v}\deg(v)=2\,|E|$ : each edge is counted once at each of its two endpoints.
• Immediate consequence: the number of vertices of ODD degree is always even.
• A spanning tree of a connected graph with $n$ vertices has exactly $n-1$ edges.
• In a directed graph, distinguish the OUT-degree, read on the row of the matrix, from the IN-degree, read on the column.

Each edge adds

1

to the degree of both its endpoints: the sum of the degrees,

12

, is twice the number of edges, and the vertices of odd degree (

B

C

D

E

) come in an even number.

The lemma is mostly used to refute: a question that announces degrees with an odd sum describes a graph that does not exist, and saying so earns the mark without any drawing.

The adjacency matrix and what you read in it

• $M_{ij}=1$ if there is an arc from $i$ to $j$ : the row gives the successors, the column the predecessors.
• $M$ is symmetric IF AND ONLY IF the graph is undirected.
• A nonzero diagonal entry signals a LOOP at the corresponding vertex.
• The sum of a row is the out-degree, the sum of a column the in-degree, and the total sum is the number of arcs.

The same graph on both sides: five arcs on the left, five entries equal to

1

on the right, and row

1

carries the two successors of vertex

1

Always write the row and column numbers around the matrix: half of all reading errors come from an entry located the wrong way round.

Powers count paths

• $(M^{k})_{ij}$ is the number of paths of length EXACTLY $k$ from $i$ to $j$ , repeated vertices being allowed.
• Reachability matrix: Boolean union of $M$ , $M^{2}$ , up to $M^{n-1}$ .
• A directed graph is strongly connected if its reachability matrix has no zero off the diagonal.

(M^{2})_{13}=1

counts the orange path

1\to 2\to 3

, of length EXACTLY

2

; the direct arc

1\to 3

, of length

1

, is counted by

M

“Exactly” is the word that costs marks: to count the paths of length AT MOST $k$ , you must add the powers, not read a single one of them.

Product, inverse and transformations

• The matrix product is associative but NOT commutative: $PQ$ and $QP$ are different in general.
• $(PQ)^{T}=Q^{T}P^{T}$ and $(PQ)^{-1}=Q^{-1}P^{-1}$ : the order is reversed.
• $\begin{pmatrix} a & b\\ c & d\end{pmatrix}^{-1}=\dfrac{1}{ad-bc}\begin{pmatrix} d & -b\\ -c & a\end{pmatrix}$ , defined only if $ad-bc\neq 0$ .
• The COLUMNS of a transformation matrix are the images of the basis vectors, and area is multiplied by $|\det|$ .

\begin{pmatrix}2&1\\0&1\end{pmatrix}

sends

\vec{i}

to its first column

(2, 0)

and

\vec{j}

to the second

(1, 1)

; the square becomes a parallelogram of area

|\det|=2

In homogeneous coordinates, a point is written $(x,y,1)$ and transformations become $3\times 3$ matrices: that is what makes it possible to write a translation as a product, and therefore to compose it with the others.

The mistakes that cost marks

These are the errors I correct most often in session. Each one costs marks on a paper, even when the reasoning behind it is right.

1. Confusing the sum of the degrees with the number of edges

1.5 marks, and a drawing that cannot be made

What not to write

“The sum of the degrees is $10$ , so the graph has $10$ edges.”

What to write

“ $\sum\deg(v)=2|E|$ , so $|E|=5$ : each edge is counted twice.”

Why: An edge has two endpoints, so it contributes one unit to each of the two degrees. That is also what rules out an odd sum of degrees.

2. Reading a directed graph as if it were undirected

2 marks, and every path computed afterwards

What not to write

“ $M_{12}=1$ , so $1$ and $2$ are linked in both directions.”

What to write

“ $M_{12}=1$ gives the arc from $1$ to $2$ ; the other direction would need $M_{21}=1$ , and the matrix is not symmetric.”

Why: Symmetry of the matrix is exactly the definition of an undirected graph. Checking this symmetry before any computation takes five seconds and avoids counting paths that do not exist.

3. Believing that a power counts the paths of at most k arcs

2 marks, it is the counting question of the test

What not to write

“ $(M^{2})_{13}=1$ , so there is only one path in all from $1$ to $3$ .”

What to write

“ $(M^{2})_{13}=1$ counts the paths of length EXACTLY $2$ ; the direct arc is counted by $M$ , which makes two paths of length at most $2$ .”

The boxed entry is

1

: a single path of length

2

from

1

3

, the one through

2

. The direct arc is counted in

M

Why: Each power isolates one length. For “at most $k$ ”, add the matrices; for “is there a path”, take the Boolean union.

4. Assuming that the matrix product is commutative

2 marks, and a wrong figure in computer graphics

What not to write

“ $PQ=QP$ , so the order of the transformations does not matter.”

What to write

“The product is NOT commutative: a rotation followed by a reflection does not give the same figure as the reflection followed by the rotation.”

The same two transformations, in both orders: the resulting figures are not the same, and neither of them is the original one.

Why: Composing means applying one, then the other: the result obviously depends on the order. The matrix applied FIRST is the one written furthest to the RIGHT in the product.

5. Transposing a product without reversing the order

1.5 marks, and often incompatible sizes

What not to write

“ $(PQ)^{T}=P^{T}Q^{T}$ .”

What to write

“ $(PQ)^{T}=Q^{T}P^{T}$ : transposition reverses the order of the factors, just like inversion.”

Why: The check is on the sizes: if $P$ is $2\times 3$ and $Q$ is $3\times 4$ , then $P^{T}Q^{T}$ is a product of a $3\times 2$ by a $4\times 3$ , which does not exist.

6. Inverting a matrix whose determinant is zero

2 marks, and the question on reversibility

What not to write

“ $\det=0$ , so $\dfrac{1}{0}$ is infinity and the inverse is very large.”

What to write

“A zero determinant means that the matrix is NOT invertible: the transformation squashes the plane onto a line.”

\begin{pmatrix}2&4\\1&2\end{pmatrix}

, whose determinant is zero, sends the square onto a segment (red): there is no way back, there is no inverse.

Why: Area is multiplied by $|\det|$ : a zero determinant flattens every figure, and lost information cannot be recovered. So the inverse does not exist, whatever value you try.

7. Reading the images of the basis vectors on the rows

1.5 marks, and a transposed transformation matrix

What not to write

“The first ROW of the matrix gives the image of the first basis vector.”

What to write

“It is the COLUMNS: the first column is the image of $\vec{i}$ , the second that of $\vec{j}$ .”

Why: Multiplying the matrix by the vector $(1, 0)$ picks out exactly the first column. The test is done in your head and settles the question in two seconds.

8. Composing the transformations in reading order

2 marks, and an object placed in the wrong spot on the screen

What not to write

“We rotate then translate, so the matrix is $R\times T$ .”

What to write

“The transformation applied FIRST goes on the RIGHT: it is $T\times R$ that rotates first, then translates.”

Rotating through

90

degrees then translating by

(3, 1)

is written

T\times R

(green);

R\times T

translates first, then rotates, and sends

P

somewhere else (red).

Why: The product acts on a vector written on the right: the matrix closest to the vector meets it first. It is the opposite of the order in which the English sentence reads.

9. Trying to write a translation as a two by two matrix

2 marks, and the requested composition becomes impossible

What not to write

“The translation by the vector $(3, 2)$ is written $\begin{pmatrix} 3 & 0\\ 0 & 2\end{pmatrix}$ .”

What to write

“A translation is not linear: it requires HOMOGENEOUS coordinates, where the point becomes $(x, y, 1)$ and the matrix $3\times 3$ .”

Why: Every $2\times 2$ matrix leaves the origin fixed, whereas a translation moves it. The constant third coordinate is precisely what makes it possible to add a vector through a product.

Which method to choose

What to read in an adjacency matrix

Look at the question asked, and at the place in the matrix that answers it.

The reachability matrix of the graph: every entry off the diagonal is

1

, so every vertex leads to every other one.

If you are asked whether the graph is directed → test symmetry: $M_{ij}=M_{ji}$ for all pairs

Example: a single asymmetric pair is enough to conclude that it is directed
If you are asked about loops → read the DIAGONAL: a nonzero entry there is a loop

Example: $M_{33}=1$ signals a loop at vertex $3$
If you are asked for a degree → sum of the row for the out-degree, of the column for the in-degree

Example: row $1$ sums to $2$ : two successors
If you are asked for the number of paths of a given length → compute $M^{k}$ and read the entry, without adding the powers

Example: $(M^{2})_{13}=1$
If you are asked whether a vertex can be reached → Boolean union of $M$ to $M^{n-1}$ , then read the entry

Example: no zero off the diagonal: strongly connected

Write the numbers around the matrix before any reading. A matrix without headings is the leading cause of an entry read the wrong way round, and the error can no longer be seen afterwards.

Which matrix for which plane transformation

Identify the transformation, then write the images of the basis vectors AS COLUMNS.

If a rotation through an angle $\theta$ about the origin → $\begin{pmatrix}\cos\theta & -\sin\theta\\ \sin\theta & \cos\theta\end{pmatrix}$ , with determinant $1$

Example: a quarter turn sends $\vec{i}$ to $\vec{j}$
If a dilation with factor $k$ → $k$ times the identity matrix, with determinant $k^{2}$

Example: area is multiplied by $k^{2}$
If a reflection across a line → determinant $-1$ : area is preserved, orientation reversed

Example: the reflection across the x-axis sends $\vec{j}$ to $-\vec{j}$
If a translation → homogeneous coordinates are required, $3\times 3$ matrix

Example: the translation vector occupies the last column
If a composition of several transformations → multiply from RIGHT to LEFT in the order of application

Example: rotating then translating is written $T\times R$

The determinant reads as a check: $1$ for a rotation, $-1$ for a reflection, $k^{2}$ for a dilation, $0$ for a projection. An unexpected value signals a column written wrong.

How the answer is expected to be written

A marker ticks steps. Here they are in order, with the concluding sentence expected word for word.

Analyzing a graph through its matrix

When to use it: The question gives a network, a traffic plan or a dependency graph and asks about paths or connectivity.

1 Number the vertices and write the matrix with its row and column headings.
2 Check consistency: number of entries equal to $1$ equal to the number of arcs, zero diagonal if the graph has no loop.
3 Compute the requested powers, stating each time which path length is being counted.
4 Conclude about the graph, not about the matrix: name the vertices and the paths in words.

Concluding sentence

“ $(M^{2})_{13}=1$ : there is a unique path of length $2$ from vertex $1$ to vertex $3$ , the one through vertex $2$ .”

The trap: Stating a result about the matrix without coming back to the graph: the conclusion mark is about the network described in the question.

Marking: 1 mark for the matrix with its headings, 1 mark per correct power, 1 mark for the conclusion in terms of vertices.

Composing plane transformations

When to use it: The question asks for the matrix of a sequence of transformations, or the image of a figure.

1 Write each transformation separately, giving the images of the basis vectors as columns.
2 Decide whether homogeneous coordinates are needed: as soon as there is a translation, they are.
3 Multiply in the REVERSE of the order of application, the first transformation on the right.
4 Check with the determinant, then apply to a simple point as a control.

Concluding sentence

“The composition is written $T\times R$ : the point is first rotated by $R$ , then moved by $T$ .”

The trap: Multiplying in the order of the sentence, which applies the transformations the wrong way round.

Marking: 1 mark per matrix written, 1 mark for the order of the product, 1 mark for the check on a point.

Check before you hand in

Five minutes of checking recover more marks than one more problem started in a hurry.

The sum of the degrees is even

Add up all the announced degrees: the total must be exactly twice the number of edges, and therefore even.

A list of degrees with sum $9$ describes a graph that does not exist.
The count of entries equal to one

Count the $1$ s in the matrix and compare with the number of arcs in the drawing.

Five arcs on the graph and six entries in the matrix: an arc was added by mistake.
The expected determinant

Rotation $1$ , reflection $-1$ , a dilation with factor $k$ gives $k^{2}$ . A determinant that does not match signals a wrong column.

A rotation whose matrix has determinant $-1$ is in fact a reflection.
The test on a simple point

Apply the composed matrix to the origin or to $(1, 0)$ and check that the image is the one expected geometrically.

A translation that leaves the origin fixed: homogeneous coordinates were forgotten.

The typical problem, taken apart

A network of four intersections

Four intersections are linked by one-way streets: from $1$ to $2$ , from $2$ to $3$ , from $3$ to $4$ , from $4$ to $1$ , and a direct street from $1$ to $3$ .

Write the adjacency matrix, count the routes of length $2$ , and say whether you can go from any intersection to any other.

The four intersections and their five one-way streets: one row of the matrix per starting intersection, one column per arrival intersection.

Step 1

Matrix $M$ : row $1$ is $0\ 1\ 1\ 0$ , row $2$ is $0\ 0\ 1\ 0$ , row $3$ is $0\ 0\ 0\ 1$ and row $4$ is $1\ 0\ 0\ 0$ .

Why

One row per STARTING intersection. Writing the headings avoids the most frequent error, which is to fill in the transposed matrix.

Step 2

Check: five entries equal to $1$ for five streets, and the diagonal is zero since no street loops back to its intersection.

Why

Two free checks before any computation. A wrong matrix at this stage makes every power wrong without anything giving it away.

Step 3

$M^{2}$ : row $1$ is $0\ 0\ 1\ 1$ , row $2$ is $0\ 0\ 0\ 1$ , row $3$ is $1\ 0\ 0\ 0$ and row $4$ is $0\ 1\ 1\ 0$ .

Why

Each entry is obtained by combining a row and a column, which amounts to chaining two arcs. Row $1$ of $M^{2}$ is the sum of rows $2$ and $3$ of $M$ .

Step 4

$(M^{2})_{13}=1$ : a single route of length $2$ from $1$ to $3$ , the one through $2$ .

Why

The direct street $1\to 3$ is NOT counted here: it has length $1$ and appears in $M$ . In all, two routes of length at most $2$ .

Step 5

Total sum of the entries of $M^{2}$ : $6$ routes of length $2$ in the whole network.

Why

The sum of all the entries of a power gives the total number of paths of that length, which provides a global check on the computation.

Step 6

Reachability: the Boolean union of $M$ , $M^{2}$ and $M^{3}$ has no zero off the diagonal.

Why

On four vertices, going up to $M^{3}$ is enough: a longer path would pass again through an intersection already visited.

The conclusion, written out

“There is a unique route of length $2$ from $1$ to $3$ , and six routes of length $2$ in all. The network is strongly connected: from any intersection, all the others can be reached.”

The classic mistake on this problem: Answering that there is only one route from $1$ to $3$ : the direct street has length $1$ and adds to the one of length $2$ .

Learn by heart

• $\sum\deg(v)=2|E|$ : the sum of the degrees is always EVEN, and so is the number of vertices of odd degree.
• $M$ symmetric if and only if the graph is undirected; a nonzero diagonal entry is a LOOP.
• $(M^{k})_{ij}$ counts the paths of length EXACTLY $k$ . For “at most”, add the powers.
• A spanning tree of a connected graph with $n$ vertices has exactly $n-1$ edges.
• $PQ\neq QP$ in general; $(PQ)^{T}=Q^{T}P^{T}$ and $(PQ)^{-1}=Q^{-1}P^{-1}$ .
• A matrix is invertible if and only if $ad-bc\neq 0$ , and area is multiplied by $|\det|$ .
• The COLUMNS of a transformation matrix are the images of the basis vectors; the first transformation applied is written on the RIGHT.
• A translation requires homogeneous coordinates: a $2\times 2$ matrix always leaves the origin fixed.

Frequently asked questions

Why does the sum of the degrees equal twice the number of edges?

Because each edge has two endpoints and therefore adds one unit to the degree of each of them. When you add up all the degrees, each edge is counted exactly twice. It follows that the sum is always even, and that the number of vertices of odd degree is even too.

What exactly does the k-th power of the adjacency matrix count?

The number of paths of length exactly k between two vertices, allowing a path to pass through the same vertex more than once. It therefore does not count shorter paths: the direct arc belongs to the matrix itself. To get the paths of at most k arcs, you must add the powers.

How do you tell whether a directed graph is strongly connected?

Build the reachability matrix, the Boolean union of the powers from one up to n minus one for n vertices. If this matrix has no zero outside the diagonal, then every vertex can reach all the others, and the graph is strongly connected.

In what order do you multiply transformation matrices?

From right to left, following the order of application. The matrix closest to the vector, so the rightmost one, acts first. Rotating then translating is therefore written translation times rotation, which is the opposite of the usual reading direction and causes most of the errors.

Why does a translation need homogeneous coordinates?

Because a two by two matrix always leaves the origin fixed, whereas a translation moves it: it is not a linear transformation. By adding a constant third coordinate equal to one, the displacement becomes a column of the three by three matrix, which makes it possible to compose it with rotations.

Practise it

Corrected exercises: Introduction to graphs and matrices, 201-N11

A method is proved on a paper, not on a sheet. The set for the same chapter takes each of these traps into a problem, with the solution written out step by step.

11 corrected exercises
110 points
150 minutes

Do the exercises

Something missing from this sheet? A method, a trap, an exercise to practise it, a mistake you spotted: tell me, I read every request.

Sending goes through your free space: that is how I can answer you and tell you when the exercise is added. An email is enough, no password. Create your space. Rather not create an account? Write to me directly.

Previous sheet Induction and recursion Next sheet Counting and probability

© Ahmed Squalli Houssaini. Revision sheet published at www.letuteurscientifique.ca/en/fiches/cegep-n11-graphs-and-matrices. Free for personal and classroom use; republishing it elsewhere requires written permission (legal notice).

Looking for a 201-N11 tutor in Montreal?

Get in touch for a first session. With a B.Sc. in computer science from McGill and an M.Sc. in applied computer science from Concordia, I connect the matrices of the course with what they drive later on: graphs, networks and what you see on the screen.

Book a session WhatsApp

Site by Studio Squalli

Revision sheet: graphs and matrices (201-N11)

The essentials

Degrees, edges and the handshaking lemma

The adjacency matrix and what you read in it

Powers count paths

Product, inverse and transformations

The mistakes that cost marks

1. Confusing the sum of the degrees with the number of edges

2. Reading a directed graph as if it were undirected

3. Believing that a power counts the paths of at most k arcs

4. Assuming that the matrix product is commutative

5. Transposing a product without reversing the order

6. Inverting a matrix whose determinant is zero

7. Reading the images of the basis vectors on the rows

8. Composing the transformations in reading order

9. Trying to write a translation as a two by two matrix

Which method to choose

What to read in an adjacency matrix

Which matrix for which plane transformation

How the answer is expected to be written

Analyzing a graph through its matrix

Composing plane transformations

Check before you hand in

The typical problem, taken apart

A network of four intersections

Learn by heart

Frequently asked questions

Why does the sum of the degrees equal twice the number of edges?

What exactly does the k-th power of the adjacency matrix count?

How do you tell whether a directed graph is strongly connected?

In what order do you multiply transformation matrices?

Why does a translation need homogeneous coordinates?

Corrected exercises: Introduction to graphs and matrices, 201-N11

See also

Looking for a 201-N11 tutor in Montreal?