8.3 The Frobenius normal form

In general, the block-matrix structure that we have just seen is called the Frobenius normal form. Here’s the precise definition.

Definition 34.

(Frobenius normal form)

Let A ∈ℝ^n×n be a nonnegative matrix. A is said to be in Frobenius normal form if it can be written in the block matrix form

where A₁,…,A_k are irreducible matrices.

Let’s reverse the question: can we transform an arbitrary nonnegative matrix into the Frobenius normal form? Yes, and with the help of directed graphs, this is much easier to show than purely using algebra. Here is the famous theorem in full form.

Theorem 54. (The existence of the Frobenius normal form)

Let A ∈ℝ^n×n be a nonnegative matrix. There exists a permutation matrix P ∈ℝ^n×n such that P^T AP is in Frobenius normal form.

Rigorously spelling out the proof of Theorem 54 is quite complicated. However, the ideas behind the...