📂Matrix Algebra

Perron-Frobenius Theorem

Theorem

Auxiliary Definitions

1. To apply a permutation on a matrix literally means to change the order of rows and columns.
2. A matrix $A$ is reducible if, after applying a permutation to $\tilde{A}$, it can be represented in the form of a Jordan block with respect to some square matrices $B, D$, a zero matrix $O$, and matrix $C$¹. If not, it is said to be irreducible.

$$ \tilde{A} = \begin{bmatrix} B & O \\ C & D \end{bmatrix} $$

Perron

For every $i,j \in \left\{ 1 , \cdots , n \right\}$, the positive matrix $A \in \mathbb{R}^{n \times n}$ always has an eigenvalue $\lambda > 0$ that satisfies the following.

• (i): $\lambda$ has an algebraic multiplicity $1$.
• (ii): All components of the eigenvector corresponding to $\lambda$ are positive.
• (iii): For all other eigenvalues $\mu$, $\lambda > \left| \mu \right|$ holds.

In other words, all eigenvalues of $A$ are positive and have a spectral radius $\rho (A)$ with an algebraic multiplicity of $1$.

Frobenius

For every $i,j \in \left\{ 1 , \cdots , n \right\}$, an irreducible non-negative matrix $A \in \mathbb{R}^{n \times n}$ always has an eigenvalue $\lambda > 0$ that satisfies all the properties mentioned in Perron’s theorem.

Explanation

Reducible Matrices

Since all positive matrices are irreducible ($\not\exist O$) and non-negative ($(A)_{ij} > 0 \ge 0$), Frobenius’ theorem generalizes Perron’s theorem. Collectively called the Perron-Frobenius theorem, it is applied in various fields such as quantum mechanics and mathematical biology. Its proof is rather long and complicated and is omitted here.²

Meanwhile, the following theorem is known about the determinant of reducible matrices.

Determinant of Block Matrices: A matrix that can be represented in the following form by applying permutations to rows and columns is called a reducible matrix, and its determinant is $\pm \det B \det D$. $$ A = \begin{bmatrix} B & O \\ C & D \end{bmatrix} $$

Graph Theory

The adjacency matrix of a simple graph is a non-negative matrix with only $0$ and $1$ as components, and especially if it is a connected graph, it satisfies all the conditions of the Perron-Frobenius theorem since there cannot exist a zero matrix as mentioned in the definition of reducible matrix $O$. In many cases, the graphs of interest in graph theory are connected simple graphs, so it can be assured that their adjacency matrices have a spectral radius unless they are uniquely peculiar.