Sunday, October 2, 2022
HomeMatlabWhat Is a Permutation Matrix? – Nick Higham

# What Is a Permutation Matrix? – Nick Higham

A permutation matrix is a sq. matrix through which each row and each column incorporates a single $1$ and all the opposite parts are zero. Such a matrix, $P$ say, is orthogonal, that’s, $P^TP = PP^T = I_n$, so it’s nonsingular and has determinant $pm 1$. The full variety of $ntimes n$ permutation matrices is $n!$.

Premultiplying a matrix by $P$ reorders the rows and postmultiplying by $P$ reorders the columns. A permutation matrix $P$ that has the specified reordering impact is constructed by doing the identical operations on the id matrix.

Examples of permutation matrices are the id matrix $I_n$, the reverse id matrix $J_n$, and the shift matrix $K_n$ (additionally referred to as the cyclic permutation matrix), illustrated for $n = 4$ by

$notag I_4 = begin{bmatrix} 1 & 0 & 0 & 0 0 & 1 & 0 & 0 0 & 0 & 1 & 0 0 & 0 & 0 & 1 end{bmatrix}, qquad J_4 = begin{bmatrix} 0 & 0 & 0 & 1 0 & 0 & 1 & 0 0 & 1 & 0 & 0 1 & 0 & 0 & 0 end{bmatrix}, qquad K_4 = begin{bmatrix} 0 & 1 & 0 & 0 0 & 0 & 1 & 0 0 & 0 & 0 & 1 1 & 0 & 0 & 0 end{bmatrix}.$

Pre- or postmultiplying a matrix by $J_n$ reverses the order of the rows and columns, respectively. Pre- or postmultiplying a matrix by $K_n$ shifts the rows or columns, respectively, one place ahead and strikes the primary one to the final place—that’s, it cyclically permutes the rows or columns. Notice that $J_n$ is a symmetric Hankel matrix and $K_n$ is a circulant matrix.

An elementary permutation matrix $P$ differs from $I_n$ in simply two rows and columns, $i$ and $j$, say. It may be written $P = I_n - (e_i-e_j)(e_i-e_j)^T$, the place $e_i$ is the $i$th column of $I_n$. Such a matrix is symmetric and so satisfies $P^2 = I_n$, and it has determinant $-1$. A common permutation matrix could be written as a product of elementary permutation matrices $P = P_1P_2dots P_k$, the place $k$ is such that $det(P) = (-1)^k$.

It’s straightforward to point out that $det(lambda I - K_n) = lambda^n - 1$, which implies that the eigenvalues of $K_n$ are $1, w, w^2, dots, w^{n-1}$, the place $w = exp(2pimathrm{i}/n)$ is the $n$th root of unity. The matrix $K_n$ has two diagonals of $1$s, which transfer up by means of the matrix as it’s powered: $K_n^i ne I$ for $i< n$ and $K_n^n = I$. The next animated gif superposes MATLAB spy plots of $K_{64}$, $K_{64}^2$, …, $K_{64}^{64} = I_{64}$.

The shift matrix $K_n$ performs a basic function in characterizing irreducible permutation matrices. Recall {that a} matrix $Ainmathbb{C}^{ntimes n}$ is irreducible if there doesn’t exist a permutation matrix $P$ such that

$notag P^TAP = begin{bmatrix} A_{11} & A_{12} 0 & A_{22} end{bmatrix},$

the place $A_{11}$ and $A_{22}$ are sq., nonempty submatrices.

Theorem 1. For a permutation matrix $P in mathbb{R}^{n times n}$ the next situations are equal.

One consequence of Theorem 1 is that for any irreducible permutation matrix $P$, $mathrm{rank}(P - I) = mathrm{rank}(K_n - I) = n-1$.

The following outcome reveals {that a} reducible permutation matrix could be expressed by way of irreducible permutation matrices.

Theorem 2. Each reducible permutation matrix is permutation much like a direct sum of irreducible permutation matrices.

One other notable permutation matrix is the vec-permutation matrix, which relates $Aotimes B$ to $Botimes A$, the place $otimes$ is the Kronecker product.

A permutation matrix is an instance of a doubly stochastic matrix: a nonnegative matrix whose row and column sums are all equal to $1$. A basic outcome characterizes doubly stochastic matrices by way of permutation matrices.

Theorem 3 (Birkhoff). A matrix is doubly stochastic if and provided that it’s a convex mixture of permutation matrices.

In coding, reminiscence could be saved by representing a permutation matrix $P$ as an integer vector $p$, the place $p_i$ is the column index of the $1$ throughout the $i$th row of $P$. MATLAB features that return permutation matrices also can return the permutation in vector type. Right here is an instance with the MATLAB `lu` operate that illustrates how permuting a matrix could be carried out utilizing the vector permutation illustration.

```>> A = gallery('frank',4), [L,U,P] = lu(A); P
A =
4     3     2     1
3     3     2     1
0     2     2     1
0     0     1     1
P =
1     0     0     0
0     0     1     0
0     0     0     1
0     1     0     0
>> P*A
ans =
4     3     2     1
0     2     2     1
0     0     1     1
3     3     2     1
>> [L,U,p] = lu(A,'vector'); p
p =
1     3     4     2
>> A(p,:)
ans =
4     3     2     1
0     2     2     1
0     0     1     1
3     3     2     1
```

For extra on dealing with permutations in MATLAB see part 24.3 of MATLAB Information.

## Notes

For proofs of Theorems 1–3 see Zhang (2011, Sec. 5.6). Theorem 3 can be proved in Horn and Johnson (2013, Thm. 8.7.2).

Permutations play a key function within the quick Fourier rework and its environment friendly implementation; see Van Mortgage (1992).

RELATED ARTICLES