Positive matrices and nonnegative matrices

course notes

Nonnegative Matrix

A nonnegative matrix is a square matrix with nonnegative entries: $A \in M_n$, $a_{ij} \ge 0, \forall i, j$, denote by $A \ge 0$. A positive matrix is a square matrix with positive entries: $A \in M_n$, $a_{ij} > 0, \forall i, j$, denote by $A > 0$.

Comparison of matrices: given $A, B \in M_n(\mathbb{R})$, $A \ge B$ iff $A - B \ge 0$; $A > B$ iff $A - B > 0$;

A nonnegative matrix $A \in M_n, n \ge 2$ need not be diagonalizable even if all the entries of $A$ are positive.

Theorem (8.1.26): Given a nonnegative matrix $A \in M_n, A \ge 0$, for all positive vector $x \in \mathbb{C}^n, x > 0$, the spectral radius $\rho(A)$ is within the intersection of the ranges of entries of $A x / x$ and $\mathrm{diag}(x)^{-1} A x$.

Corollary: If a nonnegative matrix $A \in M_n$ has a positive eigenvector, then:

  • the corresponding eigenvalue equals spectral radius $\rho(A)$, which satifies $\rho(A) = \max_{x>0} \min A x / x = \min_{x>0} \max A x / x$;
  • for all $m \in \mathbb{Z}^+$, $\max A^m \mathbf{1} \le \rho(A)^m \max x / \min x$ and $\rho(A)^m \min x / \max x \le \min A^m \mathbf{1}$.

Reducible matrix (可约化) is a square matrix that is similar to a block triangular matrix by a change of index. A system of linear equations with a block triangular coefficient matrix can be solved as a sequence of systems of linear equations whose orders sum up to the original order. Irreducible matrix is a square matrix that is not reducible. A square matrix is irreducible if and only if its (directed) graph is strongly connected.

Stochastic Matrix

A matrix is (row) stochastic if it is nonnegative and its row sums are one: $A \mathbf{1} = \mathbf{1}$. A matrix is column stochastic if it is nonnegative and its column sums are one: $\mathbf{1}^T A = \mathbf{1}^T$. A matrix is doubly stochastic if it is both row and column stochastic.

Stochastic matrices can express transition probabilities of Markov chains. Examples of doubly stochastic matrices include orthostochastic matrices $A = U \circ U^∗, U \in \mathcal{U}$ and permutation matrices $P \in S_n$.

Stochastic matrices form a compact convex set in $M_n$. Doubly stochastic matrices also form a compact convex set in $M_n$, where the extreme points are the $n!$ permutation matrices.

Theorem: If $A$ is column stochastic, then TFAE (the followings are equivalent):

  • $\lambda_{1} = \mathbf{1}$;
  • Eigenvector $\mathbf{x}_{1}$ is non-negative;
  • $| \lambda_{i} | \leq 1, \forall i \ne 1$;
  • If any power of $A$ is positive, then $\vert \lambda_{i} \vert \leq 1, \forall i \ne 1$, and $\lim_{k \to \infty} A^{k} \mathbf{u}_0 = c \mathbf{x}_1$.

Birkhoff's theorem (8.7.1): A matrix is doubly stochastic iff it is a convex combination of finitely many (at most $N = n^2 - 2n + 2$) permutation matrices.

Theorem (von Neumann): If $A, B \in M_n$, then $\mathrm{Re}(\mathrm{tr}(A B)) \le \sum_{i=n}^n \sigma_i(A) \sigma_i(B)$.

🏷 Category=Algebra Category=Matrix Analysis