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}$.

## 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.

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 Theory