Practice question · Fill in the blanks
Complete the interpretation of adjacency matrix powers.
Raising an adjacency matrix to the power k counts ______.
Word bank: the number of nodes in the network · the walks of length k between each pair of nodes · the determinant of the network · the average number of connections per node
Hints
- Each multiplication by the adjacency matrix appends one more step to every walk.
- The first power already counts the direct connections, that is, the walks of length 1.
Show the answer
Raising an adjacency matrix to the power k counts the walks of length k between each pair of nodes.
Why
Every multiplication by the adjacency matrix extends each walk by one edge, so the k-th power counts walks of length k between each pair of nodes. The row-times-column rule is exactly a sum over all possible intermediate nodes, which is why the rule is the right one for composition.
Practise Applications of Matrices and Vectors
The app has 4 more questions on this lesson, and keeps your place in the course. Mathematics I is free to start.
More questions on Applications of Matrices and Vectors
- Writing a system as Ax = b lets you solve it as x = A⁻¹b - but numerical software almost never computes the…
- Order the stages of attacking a real problem with linear algebra.
- Match each operation to the job it does.
- A three-node network has adjacency matrix with rows (0, 1, 1), (1, 0, 1) and (1, 1, 0). The entry in row 1,…
- The matrix with rows (2, 0) and (0, 2) is applied to the plane. By what factor does it multiply areas?
- Rotation by 90 degrees is the matrix with rows (0, -1) and (1, 0). Apply it to the point (3, 1). What is the…
- Sort each object by how it is naturally represented.
- Solving Ax = b by computing A⁻¹ then multiplying is mathematically correct and numerically discouraged. What…