Matrix Analysis, BIT Zhuhai. Talk 3 of the campus series

How far is the library?

Inverse matrix, determinant and Gauss–Jordan elimination, on the BIT Zhuhai campus.

On the campus map the library is one move from the dorm. Real students need 6.6 moves on average. These notes show how a determinant and an inverse matrix find that number.

Alen Serikbayev, student ID 3820261102

Dorm Library Hongyi Canteen Gym
Figure 1. On the map the library is one move from the dorm (grey line). Real walks wander (black line): 6.6 moves on average.

1Start small: three places, one rule book

Last time we wrote students’ habits as a matrix P. A row is where people leave from, a column is where they go, and every row adds up to 1.

Then we asked where students spend their time: Hongyi, about 30%. Today we ask how long it takes to get somewhere. First on three places, then on the real campus.

Figure 2. The rules P for three places. Morning: everyone goes from the dorm to class. After class, half go home and half go to eat.

2One move = one walk between two places

Not meters, not minutes. Dorm to Hongyi is one move. A student keeps moving by the rules of P until the first arrival at the canteen, and we count the moves.

Dorm Hongyi Canteen finish 1 ½ ½
Moves: 0Dorm
Figure 3. One student walking by P. Each arrow taken is one move.

Every walk is different, so we want the average. Three unknowns:

tD from the dormtH from HongyitC = 0, already there

3Try it before any formula

The black dot is one student who starts in the dorm. At Hongyi it is a coin flip: home or lunch. Watch a few walks, then let the computer walk 10 000 times.

It starts by itself when you scroll here.

moves per walk

?average after 0 walks
Figure 4. Grey bars: share of walks with each length. Black marks: theory, ½, ¼, ⅛ …

Every walk is different, but the average settles near 4.

4Think one move ahead

Average moves from a place = 1 move now + the average from where you land.

tH = 1 + ½ tD + ½ · 0(4.1)
tD = 1 + tH(4.2)
tH = 1 + ½ (1 + tH) = 1.5 + ½ tH(4.3)
½ tH = 1.5sotH = 3(4.4)
tD = 1 + 3 = 4(4.5)

Picture 100 students in Hongyi. Every one of them makes one move.

Half go home: they still need tD moves. Half reach the canteen: they need nothing more. This is (4.1).

From the dorm there is only one way: everyone walks back to Hongyi. One move, then tH more. This is (4.2).

Two equations, two unknowns. Put (4.2) into (4.1) and collect tH on one side.

tH = 3 and tD = 4. The 10 000 walks said about 4. Same answer, no computer.

Step

5Two equations, one matrix

Three places are easy by hand. Five places, or a graph with a million nodes, need one method that works for any size.

P, the rules

Q t = 01½0 tDtH = tH½ tD (5.1)
(I − Q) t = 1,  I − Q = 1−1−½1 (5.2)

Start from P, the same table as before.

The canteen is the finish, so its row and column no longer matter. Cross them out. What is left is Q: the moves that are not finished yet.

Multiply Q by t = (tD, tH). Row by row you get tH and ½ tD: exactly what comes after “1 +” in (4.1) and (4.2).

So both equations are one line, t = 1 + Q t. Move Q t to the left. If the inverse exists, t = (I − Q)−1 1.

Step

6Is there an answer at all?

An inverse exists only when the determinant is not zero. For a 2 × 2 matrix: the main diagonal minus the other diagonal.

det abcd = ad − bc
det(I − Q) = 1 · 1 − (−1)(−½) = 1 − ½ = ½(6.1)

½ is not 0, so the inverse exists, and so does the answer.

What the number means here

Students circle between the dorm and Hongyi. The canteen is the only exit. Change how many take the exit.

det(I − Q)0.50

moves from the dorm4.0

moves from Hongyi3.0

Figure 5. With a share p the determinant is p and the dorm needs 2/p moves. At p = 0 there is no inverse.

7Gauss–Jordan elimination

The 2 × 2 formula only works for 2 × 2. Row operations work for any size, and they are what a computer does.

Write I − Q and put the identity next to it. We only use row operations until the left side becomes I.

Step 1. Make a 0 under the pivot: add half of row 1 to row 2. Under each cell you see its sum.

Step 2. Make the pivot 1: multiply row 2 by 2.

Step 3. Make a 0 above the pivot: add row 2 to row 1. The left side is I, so the right side is (I − Q)−1.

Multiplying by 1 = (1, 1) adds up each row: 4 moves from the dorm, 3 from Hongyi. Same as (4.5).

Bonus: in step 1 the diagonal held 1 and ½. Their product, ½, is the determinant (6.1).

Step

8Back to the real campus

Five places, and the library is the finish. The same three steps give the averages: Q is 4 × 4, det(I − Q) ≈ 0.34, so the inverse exists, and Gauss–Jordan runs on a computer.

Dorm
Canteen
Hongyi
Gym
Library
Figure 6. Each dot is one student walking by the campus matrix P. A ring at the library is one finished walk.
Table 1. Average moves to the library.
FromMoves
Hongyi0.0
Canteen0.0
Dorm0.0
Gym0.0

9The shortest path is not how people move

My first topic found the shortest way. Today’s number counts how students really walk. In graph analysis it is called the hitting time: the average number of random steps to reach a node.

Shortest path on the map0 moves
One real student, following P0 moves
Figure 7. The map edge is one move. A real walk wanders; this one took 8 moves, and the average is 6.6.

A small hitting time means two places, two people in a social network or two web pages are closely connected. The formula stays the same for very large graphs; only Q gets bigger. That is why it matters for my course, Large Graph Data Analysis.

10Three things to keep

  1. Average moves = 1 + the average from where you land

    As a matrix: (I − Q) t = 1, so t = (I − Q)−1 1.

  2. A non-zero determinant means an answer exists

    Here the determinant is the chance to leave the dorm–Hongyi loop. At 0 nobody ever arrives.

  3. Gauss–Jordan turns [AI] into [IA−1]

    It works for any size, and the pivots multiply to the determinant.