---
title: "PermutationMatrix"
language: "en"
type: "Symbol"
summary: "PermutationMatrix[permv] represents the permutation matrix given by permutation vector permv as a structured array. PermutationMatrix[pmat] converts a permutation matrix pmat to a structured array."
keywords: 
- permutation matrix
- structured array
- structuredarray
canonical_url: "https://reference.wolfram.com/language/ref/PermutationMatrix.html"
source: "Wolfram Language Documentation"
related_guides: 
  - 
    title: "Structured Arrays"
    link: "https://reference.wolfram.com/language/guide/StructuredArrays.en.md"
related_functions: 
  - 
    title: "Cycles"
    link: "https://reference.wolfram.com/language/ref/Cycles.en.md"
  - 
    title: "PermutationCycles"
    link: "https://reference.wolfram.com/language/ref/PermutationCycles.en.md"
  - 
    title: "PermutationList"
    link: "https://reference.wolfram.com/language/ref/PermutationList.en.md"
  - 
    title: "Permute"
    link: "https://reference.wolfram.com/language/ref/Permute.en.md"
  - 
    title: "LUDecomposition"
    link: "https://reference.wolfram.com/language/ref/LUDecomposition.en.md"
  - 
    title: "QRDecomposition"
    link: "https://reference.wolfram.com/language/ref/QRDecomposition.en.md"
---
# PermutationMatrix

PermutationMatrix[permv] represents the permutation matrix given by permutation vector permv as a structured array.

PermutationMatrix[pmat] converts a permutation matrix pmat to a structured array.

## Details and Options

* Permutation matrices, when represented as structured arrays, allow for efficient storage and more efficient operations, including ``Det``, ``Inverse`` and ``LinearSolve``.

* Permutation matrices typically occur in the output from matrix decomposition algorithms to represent row or column permutations (usually termed pivoting in that context).

* Given a permutation vector $\left\{p_1,\ldots ,p_n\right\}$, the resulting permutation matrix $P$ is given by $P[[i,j]]=\delta _{i,p_j}$. This corresponds to a matrix that has a one in column $p_j$ of row $i$ and zeros elsewhere.

[image]

* A permutation matrix $P$ can be used to permute rows by multiplying from the left $P.A$ or permute columns by multiplying its transpose from the right $A.P^T$.

* A permutation matrix $P$ is an orthogonal matrix, where the inverse is equivalent to the transpose $P^{-1}=P^T$.

* Permutation matrices are closed under matrix multiplication, so $P_1.P_2$ is again a permutation matrix.

* The determinant of a permutation matrix is either $-1$ or 1 and equals ``Signature[permv]``.

* Operations that are accelerated for ``PermutationMatrix`` include:

|             |                                           |
| ----------- | ----------------------------------------- |
| Det         | time $O(n)$ |
| Dot         | time $O(n)$ |
| Inverse     | time $O(n)$ |
| LinearSolve | time $O(n)$ |

* For a ``PermutationMatrix`` ``sa``, the following properties ``"prop"`` can be accessed as ``sa["prop"]`` :

|                        |                                                                 |
| ---------------------- | --------------------------------------------------------------- |
| "PermutationCycles"    | disjoint cycle representation of the permutation matrix         |
| "PermutationList"      | permutation list representation of the permutation matrix       |
| "WorkingPrecision"     | precision used internally                                       |
| "Properties"           | list of supported properties                                    |
| "Structure"            | type of structured array                                        |
| "StructuredData"       | internal data stored by the structured array                    |
| "StructuredAlgorithms" | list of functions with special methods for the structured array |
| "Summary"              | summary information, represented as a Dataset                   |

* ``Normal[PermutationMatrix[…]]`` gives the permutation matrix as an ordinary matrix.

* The following options can be given:

|                   |           |                                      |
| ----------------- | --------- | ------------------------------------ |
| TargetStructure   | Automatic | the structure of the returned matrix |
| WorkingPrecision  | Infinity  | precision at which to create entries |

* Possible settings for ``TargetStructure`` include:

|              |                                                  |
| ------------ | ------------------------------------------------ |
| Automatic    | automatically choose the representation returned |
| "Dense"      | represent the matrix as a dense matrix           |
| "Orthogonal" | represent the matrix as an orthogonal matrix     |
| "Sparse"     | represent the matrix as a sparse array           |
| "Structured" | represent the matrix as a structured array       |
| "Unitary"    | represent the matrix as a unitary matrix         |

* ``PermutationMatrix[…, TargetStructure -> Automatic]`` is equivalent to ``PermutationMatrix[…, TargetStructure -> "Structured"]``.

---

## Examples (22)

### Basic Examples (2)

Construct a permutation matrix from a permutation vector:

```wl
In[1]:= pm = PermutationMatrix[{4, 1, 3, 2}]

Out[1]= PermutationMatrix[StructuredArray`StructuredData[{4, 4}, {Cycles[{{1, 4, 2}}], Infinity}]]
```

Show the elements:

```wl
In[2]:= MatrixForm[pm]

Out[2]//MatrixForm=
(⁠|   |   |   |   |
| - | - | - | - |
| 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |⁠)
```

Get the normal representation:

```wl
In[3]:= Normal[pm]

Out[3]= {{0, 0, 0, 1}, {1, 0, 0, 0}, {0, 0, 1, 0}, {0, 1, 0, 0}}
```

---

Represent a permutation matrix as a structured array:

```wl
In[1]:= pm = PermutationMatrix[{{0, 1, 0}, {0, 0, 1}, {1, 0, 0}}]

Out[1]= PermutationMatrix[StructuredArray`StructuredData[{3, 3}, {Cycles[{{1, 2, 3}}], Infinity}]]
```

Show the elements:

```wl
In[2]:= MatrixForm[pm]

Out[2]//MatrixForm=
(⁠|   |   |   |
| - | - | - |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
| 1 | 0 | 0 |⁠)
```

Compute the determinant:

```wl
In[3]:= Det[pm]

Out[3]= 1
```

### Scope (7)

Construct a permutation matrix from a disjoint cycle representation:

```wl
In[1]:= pm = PermutationMatrix[Cycles[{{1, 4, 3}, {2, 5}}]]

Out[1]= PermutationMatrix[StructuredArray`StructuredData[{5, 5}, {Cycles[{{1, 4, 3}, {2, 5}}], Infinity}]]
```

Show the elements:

```wl
In[2]:= MatrixForm[pm]

Out[2]//MatrixForm=
(⁠|   |   |   |   |   |
| - | - | - | - | - |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 |⁠)
```

Get the normal representation:

```wl
In[3]:= Normal[pm]

Out[3]= {{0, 0, 0, 1, 0}, {0, 0, 0, 0, 1}, {1, 0, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 1, 0, 0, 0}}
```

Specify the dimension of the permutation matrix:

```wl
In[4]:= pm = PermutationMatrix[Cycles[{{1, 4, 3}, {2, 5}}], 7]

Out[4]= PermutationMatrix[StructuredArray`StructuredData[{7, 7}, {Cycles[{{1, 4, 3}, {2, 5}}], Infinity}]]
```

Show the elements:

```wl
In[5]:= MatrixForm[pm]

Out[5]//MatrixForm=
(⁠|   |   |   |   |   |   |   |
| - | - | - | - | - | - | - |
| 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 |⁠)
```

---

Construct a permutation matrix from a ``TwoWayRule`` (an interchange permutation):

```wl
In[1]:= pm = PermutationMatrix[2 <-> 6]

Out[1]= PermutationMatrix[StructuredArray`StructuredData[{6, 6}, {Cycles[{{2, 6}}], Infinity}]]
```

Show the elements:

```wl
In[2]:= MatrixForm[pm]

Out[2]//MatrixForm=
(⁠|   |   |   |   |   |   |
| - | - | - | - | - | - |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 |⁠)
```

Get the normal representation:

```wl
In[3]:= Normal[pm]

Out[3]= {{1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1}, {0, 0, 1, 0, 0, 0}, {0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 1, 0}, {0, 1, 0, 0, 0, 0}}
```

Specify the dimension of the permutation matrix:

```wl
In[4]:= pm = PermutationMatrix[2 <-> 6, 7]

Out[4]= PermutationMatrix[StructuredArray`StructuredData[{7, 7}, {Cycles[{{2, 6}}], Infinity}]]
```

Show the elements:

```wl
In[5]:= MatrixForm[pm]

Out[5]//MatrixForm=
(⁠|   |   |   |   |   |   |   |
| - | - | - | - | - | - | - |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 |⁠)
```

---

Construct a permutation matrix from an explicit matrix:

```wl
In[1]:=
pm = PermutationMatrix[(⁠|   |   |   |   |   |   |   |   |
| - | - | - | - | - | - | - | - |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |⁠)]

Out[1]=
PermutationMatrix[StructuredArray`StructuredData[{8, 8}, {Cycles[{{2, 3, 5}, {4, 7, 6}}], 
   Infinity}]]
```

Show the elements:

```wl
In[2]:= MatrixForm[pm]

Out[2]//MatrixForm=
(⁠|   |   |   |   |   |   |   |   |
| - | - | - | - | - | - | - | - |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |⁠)
```

Get the normal representation:

```wl
In[3]:= Normal[pm]

Out[3]= {{1, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 0}, {0, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1}}
```

---

``PermutationMatrix`` objects include properties that give information about the array:

```wl
In[1]:= pm = PermutationMatrix[RandomSample[1 ;; 47]]

Out[1]=
PermutationMatrix[StructuredArray`StructuredData[{47, 47}, 
  {Cycles[{{1, 42, 22, 35, 14, 7, 41, 23, 29, 30, 36, 20, 2, 25, 32, 33, 15, 21, 24, 5, 45, 39, 13, 
      12, 37, 43, 28, 46, 8, 26, 6, 10, 4, 31, 19}, {3, 9, 17, 11, 16, 47}, 
     {18, 44, 27, 38, 40, 34}}], Infinity}]]

In[2]:= pm["Properties"]

Out[2]= {"PermutationCycles", "PermutationList", "WorkingPrecision", "Properties", "Structure", "StructuredData", "StructuredAlgorithms", "Summary"}
```

``"PermutationCycles"`` gives the disjoint cycle representation of the underlying permutation:

```wl
In[3]:= pm["PermutationCycles"]

Out[3]= Cycles[{{1, 42, 22, 35, 14, 7, 41, 23, 29, 30, 36, 20, 2, 25, 32, 33, 15, 21, 24, 5, 45, 39, 13, 12, 37, 43, 28, 46, 8, 26, 6, 10, 4, 31, 19}, {3, 9, 17, 11, 16, 47}, {18, 44, 27, 38, 40, 34}}]
```

``"PermutationList"`` gives the permutation list representation:

```wl
In[4]:= pm["PermutationList"]

Out[4]= {42, 25, 9, 31, 45, 10, 41, 26, 17, 4, 16, 37, 12, 7, 21, 47, 11, 44, 1, 2, 24, 35, 29, 5, 32, 6, 38, 46, 30, 36, 19, 33, 15, 18, 14, 20, 43, 40, 13, 34, 23, 22, 28, 27, 39, 8, 3}
```

``"WorkingPrecision"`` gives the precision of the matrix entries:

```wl
In[5]:= pm["WorkingPrecision"]

Out[5]= ∞
```

The ``"Summary"`` property gives a brief summary of information about the array:

```wl
In[6]:= pm["Summary"]

Out[6]= Dataset[Association["Structure" -> PermutationMatrix, "Dimensions" -> {47, 47}]]
```

The ``"StructuredAlgorithms"`` property lists the functions that have structured algorithms:

```wl
In[7]:= pm["StructuredAlgorithms"]

Out[7]= {Conjugate, ConjugateTranspose, Det, Diagonal, Dot, Eigensystem, Eigenvalues, Eigenvectors, Inverse, KroneckerProduct, LeastSquares, LinearSolve, LUDecomposition, MatrixPower, MatrixRank, Norm, PseudoInverse, QRDecomposition, SingularValueDecomposition, SingularValueList, Tr, Transpose}
```

---

Structured algorithms are typically faster:

```wl
In[1]:= pm  = PermutationMatrix[Cycles[{{1, 131}, {3, 765}}]]

Out[1]=
PermutationMatrix[StructuredArray`StructuredData[{765, 765}, 
  {Cycles[{{1, 131}, {3, 765}}], Infinity}]]

In[2]:= pn = Normal[pm];
```

Compute the determinant:

```wl
In[3]:= AbsoluteTiming[Det[pn]]

Out[3]= {0.405366, 1}

In[4]:= AbsoluteTiming[Det[pm]]

Out[4]= {0.000049, 1}
```

Compute the inverse:

```wl
In[5]:= AbsoluteTiming[Inverse[pn];]

Out[5]= {0.165553, Null}

In[6]:= AbsoluteTiming[Inverse[pm];]

Out[6]= {0.0001848, Null}
```

Compute the eigenvalues:

```wl
In[7]:= AbsoluteTiming[Eigenvalues[pn];]

Out[7]= {9.88143, Null}

In[8]:= AbsoluteTiming[Eigenvalues[pm];]

Out[8]= {0.0002458, Null}
```

---

When appropriate, structured algorithms return another ``PermutationMatrix`` object:

```wl
In[1]:=
perm = {1, 5, 3, 2, 4};
pm = PermutationMatrix[perm]

Out[1]= PermutationMatrix[StructuredArray`StructuredData[{5, 5}, {Cycles[{{2, 5, 4}}], Infinity}]]
```

The inverse allows you to easily get the inverse permutation:

```wl
In[2]:= Inverse[pm]

Out[2]= PermutationMatrix[StructuredArray`StructuredData[{5, 5}, {Cycles[{{2, 4, 5}}], Infinity}]]

In[3]:= pinv = PermutationList[%]

Out[3]= {1, 4, 3, 5, 2}
```

Verify the inverse relationship:

```wl
In[4]:= perm[[pinv]] == Range[Length[perm]]

Out[4]= True
```

This is equivalent to the result of ``InversePermutation`` :

```wl
In[5]:= pinv === InversePermutation[perm]

Out[5]= True
```

---

Generate a random ``10^4×10^4`` permutation vector:

```wl
In[1]:= perm = PermutationList[RandomPermutation[1*^4]];
```

The representation and computation are efficient for the structured array:

```wl
In[2]:= PermutationMatrix[perm]//ByteCount//AbsoluteTiming

Out[2]= {0.0002448, 84536}

In[3]:= Inverse[PermutationMatrix[perm]]//ByteCount//AbsoluteTiming

Out[3]= {0.0007048, 84536}
```

The normal representation is dramatically bigger (80 KB vs. 800 MB) and slower:

```wl
In[4]:= (pnormal = Normal@PermutationMatrix[perm])//ByteCount//AbsoluteTiming

Out[4]= {0.136703, 800000208}
```

The inverse needs 2.4 GB of storage:

```wl
In[5]:= Inverse[pnormal]//ByteCount//AbsoluteTiming

Out[5]= {17.5993, 2400880080}
```

### Options (2)

#### TargetStructure (1)

Return the permutation matrix as a dense matrix:

```wl
In[1]:= PermutationMatrix[Cycles[{{4, 1, 3}}], TargetStructure -> "Dense"]

Out[1]= {{0, 0, 1, 0}, {0, 1, 0, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}}
```

Return the permutation matrix as a structured array:

```wl
In[2]:= PermutationMatrix[Cycles[{{4, 1, 3}}], TargetStructure -> "Structured"]

Out[2]= PermutationMatrix[StructuredArray`StructuredData[{4, 4}, {Cycles[{{1, 3, 4}}], Infinity}]]
```

Return the permutation matrix as a sparse array:

```wl
In[3]:= PermutationMatrix[Cycles[{{4, 1, 3}}], TargetStructure -> "Sparse"]

Out[3]= SparseArray[Automatic, {4, 4}, 0, {1, {{0, 1, 2, 3, 4}, {{3}, {2}, {4}, {1}}}, {1, 1, 1, 1}}]
```

Return the permutation matrix as an orthogonal matrix:

```wl
In[4]:= PermutationMatrix[Cycles[{{4, 1, 3}}], TargetStructure -> "Orthogonal"]

Out[4]=
OrthogonalMatrix[StructuredArray`StructuredData[{4, 4}, 
  {SparseArray[Automatic, {4, 4}, 0, {1, {{0, 1, 2, 3, 4}, {{3}, {2}, {4}, {1}}}, {1, 1, 1, 1}}], 
   0}]]
```

Return the permutation matrix as a unitary matrix:

```wl
In[5]:= PermutationMatrix[Cycles[{{4, 1, 3}}], TargetStructure -> "Unitary"]

Out[5]=
UnitaryMatrix[StructuredArray`StructuredData[{4, 4}, 
  {SparseArray[Automatic, {4, 4}, 0, {1, {{0, 1, 2, 3, 4}, {{3}, {2}, {4}, {1}}}, {1, 1, 1, 1}}], 
   0}]]
```

#### WorkingPrecision (1)

Specify the working precision for the permutation matrix:

```wl
In[1]:= pm = PermutationMatrix[{4, 1, 3, 2}, WorkingPrecision -> MachinePrecision]

Out[1]= PermutationMatrix[StructuredArray`StructuredData[{4, 4}, {Cycles[{{1, 4, 2}}], MachinePrecision}]]
```

The normal representation returns a full matrix with finite precision elements:

```wl
In[2]:= Normal[pm]

Out[2]= {{0., 0., 0., 1.}, {1., 0., 0., 0.}, {0., 0., 1., 0.}, {0., 1., 0., 0.}}
```

### Applications (4)

A function for computing the LU decomposition of a matrix:

```wl
In[1]:=
luDecomposition[mat_ ? SquareMatrixQ] := Module[{luList = LUDecomposition[mat], lu}, 
	lu = First[luList];
	{LowerTriangularMatrix[LowerTriangularize[lu, -1] + IdentityMatrix[Length[mat]]], UpperTriangularMatrix[UpperTriangularize[lu]], PermutationMatrix[luList[[2]]]}]
```

Compute the decomposition:

```wl
In[2]:=
a = {{4, 9, 2}, {2, 3, 2}, {7, 2, 4}};
{lt, ut, pm} = luDecomposition[a]

Out[2]=
{LowerTriangularMatrix[StructuredArray`StructuredData[{3, 3}, 
  {{1, 0, 0}, {2, 1, 0}, {Rational[7, 2], Rational[-17, 6], 1}}]], UpperTriangularMatrix[StructuredArray`StructuredData[{3, 3}, 
  {{2, 3, 2}, {0, 3, -2}, {0, 0, Rational[-26, 3]}}]], PermutationMatrix[StructuredArray`StructuredData[{3, 3}, {Cycles[{{1, 2}}], Infinity}]]}
```

Verify the decomposition:

```wl
In[3]:= lt.ut == pm.a

Out[3]= True
```

---

Generate permutation matrices corresponding to the elements of a permutation group:

```wl
In[1]:=
n = 5;
group = DihedralGroup[n];
elems = PermutationMatrix[#, n]& /@ GroupElements[group]

Out[1]= {PermutationMatrix[StructuredArray`StructuredData[{5, 5}, {Cycles[{}], Infinity}]], PermutationMatrix[StructuredArray`StructuredData[{5, 5}, {Cycles[{{2, 5}, {3, 4}}], Infinity}]], PermutationMatrix[StructuredArray`StructuredData[{5, 5}, {Cycles[{{ ... ata[{5, 5}, {Cycles[{{1, 4, 2, 5, 3}}], Infinity}]], PermutationMatrix[StructuredArray`StructuredData[{5, 5}, {Cycles[{{1, 5, 4, 3, 2}}], Infinity}]], PermutationMatrix[StructuredArray`StructuredData[{5, 5}, {Cycles[{{1, 5}, {2, 4}}], Infinity}]]}
```

Compute a multiplication table for the group:

```wl
In[2]:= Outer[Position[elems, Dot[#1, #2]][[1, 1]]&, elems, elems, 1]

Out[2]= {{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {2, 1, 4, 3, 6, 5, 8, 7, 10, 9}, {3, 9, 1, 5, 4, 7, 6, 10, 2, 8}, {4, 10, 2, 6, 3, 8, 5, 9, 1, 7}, {5, 8, 9, 7, 1, 10, 4, 2, 3, 6}, {6, 7, 10, 8, 2, 9, 3, 1, 4, 5}, {7, 6, 8, 10, 9, 2, 1, 3, 5, 4}, {8, 5, 7, 9, 10, 1, 2, 4, 6, 3}, {9, 3, 5, 1, 7, 4, 10, 6, 8, 2}, {10, 4, 6, 2, 8, 3, 9, 5, 7, 1}}
```

This is equivalent to the result of ``GroupMultiplicationTable`` :

```wl
In[3]:= % === GroupMultiplicationTable[group]

Out[3]= True
```

---

Define the vec operator, which stacks the columns of a matrix into a single vector:

```wl
In[1]:= vec[m_ ? MatrixQ] := Flatten[m, {{2, 1}}]
```

Define the vec-permutation matrix, also called the commutation matrix:

```wl
In[2]:= vecPermutationMatrix[p_, q_] := PermutationMatrix[Flatten[Partition[Range[p q], p], {{2, 1}}]]
```

The vec-permutation matrix relates the result of applying the vec operator to a matrix and its transpose:

```wl
In[3]:=
p = 4;q = 3;
m1 = Array[\[FormalX], {p, q}];
vec[Transpose[m1]] == vecPermutationMatrix[p, q].vec[m1]

Out[3]= True
```

The vec-permutation matrix can be used to express the relationship between the Kronecker product of two given matrices and the Kronecker product of the same matrices in reverse order:

```wl
In[4]:=
r = 4;s = 3;
m2 = Array[\[FormalY], {r, s}];
KroneckerProduct[m1, m2].vecPermutationMatrix[q, s] == vecPermutationMatrix[p, r].KroneckerProduct[m2, m1]

Out[4]= True
```

---

The efficiency of the fast Fourier transform (FFT) relies on being able to form a larger Fourier matrix from two smaller ones. Generate two small Fourier matrices of sizes ``p`` and ``q`` :

```wl
In[1]:=
p = 2;
MatrixForm[fmatp = FourierMatrix[p]]

Out[1]//MatrixForm=
(⁠|             |              |
| ----------- | ------------ |
| (1/Sqrt[2]) | (1/Sqrt[2])  |
| (1/Sqrt[2]) | -(1/Sqrt[2]) |⁠)

In[2]:=
q = 3;
MatrixForm[fmatq = FourierMatrix[q]]

Out[2]//MatrixForm=
(⁠|             |                        |                        |
| ----------- | ---------------------- | ---------------------- |
| (1/Sqrt[3]) | (1/Sqrt[3])            | (1/Sqrt[3])            |
| (1/Sqrt[3]) | (E^(2 I π/3)/Sqrt[3])  | (E^-(2 I π/3)/Sqrt[3]) |
| (1/Sqrt[3]) | (E^-(2 I π/3)/Sqrt[3]) | (E^(2 I π/3)/Sqrt[3])  |⁠)
```

The Fourier matrix of size ``p q`` can be expressed as a product of four simpler matrices:

```wl
In[3]:=
fpkp = KroneckerProduct[fmatp, IdentityMatrix[q]];
diag = DiagonalMatrix[Flatten[Table[Exp[(2 π I j k/p q)], {k, 0, p - 1}, {j, 0, q - 1}]]];
fqkp = BlockDiagonalMatrix[ConstantArray[fmatq, p]];
shuffle = PermutationMatrix[Flatten[Partition[Range[p q], p], {{2, 1}}]];
MatrixForm[fmatpq = fpkp.diag.fqkp.shuffle]

Out[3]//MatrixForm=
(⁠|             |                        |                        |              |                        |                         |
| ----------- | ---------------------- | ---------------------- | ------------ | ---------------------- | -------- ... E^(I π/3)/Sqrt[6])   | (E^(2 I π/3)/Sqrt[6])  | (1/Sqrt[6])  | (E^-(2 I π/3)/Sqrt[6]) | -(E^-(I π/3)/Sqrt[6])   |
| (1/Sqrt[6]) | -(E^(2 I π/3)/Sqrt[6]) | (E^-(2 I π/3)/Sqrt[6]) | -(1/Sqrt[6]) | (E^(2 I π/3)/Sqrt[6])  | -(E^-(2 I π/3)/Sqrt[6]) |⁠)
```

Show that the resulting matrix is equivalent to the result of ``FourierMatrix`` :

```wl
In[4]:= fmatpq == FourierMatrix[p q]

Out[4]= True
```

The discrete Fourier transform of a vector can be computed by successively multiplying the factors of the Fourier matrix to the vector:

```wl
In[5]:=
data = RandomComplex[1 + I, p q];
res = fpkp.(diag.(fqkp.(shuffle.data)))

Out[5]= {0.826148  + 1.22454 I, 0.238643  + 0.0352713 I, -0.201243 - 0.491225 I, 0.257289  + 0.0912065 I, -0.207466 - 0.64845 I, -0.25516 - 0.0946359 I}
```

The result is equivalent to applying ``Fourier`` to the vector:

```wl
In[6]:= Chop[Max[Abs[res - Fourier[data]]]] == 0

Out[6]= True
```

### Properties & Relations (6)

Convert an identity matrix to a permutation matrix:

```wl
In[1]:= PermutationMatrix[IdentityMatrix[5]]

Out[1]= PermutationMatrix[StructuredArray`StructuredData[{5, 5}, {Cycles[{}], Infinity}]]
```

Show the disjoint cycle representation:

```wl
In[2]:= PermutationCycles[%]

Out[2]= Cycles[{}]
```

---

``PermutationMatrix[p <-> q]`` is equivalent to ``PermutationMatrix[Cycles[{{p, q}}]]`` :

```wl
In[1]:= p1 = PermutationMatrix[2 <-> 7]

Out[1]= PermutationMatrix[StructuredArray`StructuredData[{7, 7}, {Cycles[{{2, 7}}], Infinity}]]

In[2]:= p2 = PermutationMatrix[Cycles[{{2, 7}}]]

Out[2]= PermutationMatrix[StructuredArray`StructuredData[{7, 7}, {Cycles[{{2, 7}}], Infinity}]]

In[3]:= p1 === p2

Out[3]= True
```

---

Use ``SparseArray[PermutationMatrix[…]]`` to get a representation as a ``SparseArray`` :

```wl
In[1]:= SparseArray[PermutationMatrix[Cycles[{{1, 18, 7}, {2, 5, 4, 10}}]]]

Out[1]=
SparseArray[Automatic, {18, 18}, 0, 
 {1, {{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18}, 
   {{18}, {5}, {3}, {10}, {4}, {6}, {1}, {8}, {9}, {2}, {11}, {12}, {13}, {14}, {15}, {16}, {17}, 
    {7}}}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}}]
```

---

Generate a random permutation list:

```wl
In[1]:= perm = RandomSample[1 ;; 5]

Out[1]= {2, 1, 3, 4, 5}
```

Premultiplication with a permutation matrix is equivalent to using ``Part`` with a permutation list:

```wl
In[2]:=
v = RandomReal[1, 5];
v[[perm]]

Out[2]= {0.354155, 0.407255, 0.421781, 0.346149, 0.511025}

In[3]:= pm = PermutationMatrix[perm]

Out[3]= PermutationMatrix[StructuredArray`StructuredData[{5, 5}, {Cycles[{{1, 2}}], Infinity}]]

In[4]:= pm.v

Out[4]= {0.354155, 0.407255, 0.421781, 0.346149, 0.511025}
```

Postmultiplication with a permutation matrix is equivalent to using ``Permute`` with a permutation list:

```wl
In[5]:= Permute[v, perm]

Out[5]= {0.354155, 0.407255, 0.421781, 0.346149, 0.511025}

In[6]:= v.pm

Out[6]= {0.354155, 0.407255, 0.421781, 0.346149, 0.511025}
```

---

The determinant of a permutation matrix is equal to the signature of the corresponding permutation list:

```wl
In[1]:= perm = RandomSample[1 ;; 7]

Out[1]= {7, 4, 6, 2, 5, 1, 3}

In[2]:= pm = PermutationMatrix[perm]

Out[2]=
PermutationMatrix[StructuredArray`StructuredData[{7, 7}, {Cycles[{{1, 7, 3, 6}, {2, 4}}], 
   Infinity}]]

In[3]:= Det[pm] == Signature[perm]

Out[3]= True
```

---

The permanent of the product of a permutation matrix and a general matrix is equal to the permanent of the original matrix:

```wl
In[1]:=
n = 5;
perm = PermutationMatrix[RandomSample[1 ;; n]];
mat = Array[C, {n, n}];

In[2]:= Permanent[perm.mat] == Permanent[mat.perm] == Permanent[mat]//Simplify

Out[2]= True
```

### Neat Examples (1)

An upper bidiagonal matrix:

```wl
In[1]:= MatrixForm[bi = Normal[SparseArray[{Band[{1, 1}] -> Array[\[FormalD], 5], Band[{1, 2}] -> Array[\[FormalE], 4]}]]]

Out[1]//MatrixForm=
(⁠|      |      |      |      |      |
| ---- | ---- | ---- | ---- | ---- |
| \[FormalD][1] | \[FormalE][1] | 0    | 0    | 0    |
| 0    | \[FormalD][2] | \[FormalE][2] | 0    | 0    |
| 0    | 0    | \[FormalD][3] | \[FormalE][3] | 0    |
| 0    | 0    | 0    | \[FormalD][4] | \[FormalE][4] |
| 0    | 0    | 0    | 0    | \[FormalD][5] |⁠)
```

Generate a symmetric block matrix with bidiagonal blocks (a Jordan–Wielandt matrix):

```wl
In[2]:= MatrixForm[biblk = ArrayFlatten[{{0, Transpose[bi]}, {bi, 0}}]]

Out[2]//MatrixForm=
(⁠|      |      |      |      |      |      |      |      |      |      |
| ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 0    | 0    | 0    | 0    | 0    | \[FormalD][1] | 0    | 0    | 0    | 0    |
| 0    | 0    | 0    | 0    |  ... | 0    | 0    | 0    | 0    |
| 0    | 0    | \[FormalD][3] | \[FormalE][3] | 0    | 0    | 0    | 0    | 0    | 0    |
| 0    | 0    | 0    | \[FormalD][4] | \[FormalE][4] | 0    | 0    | 0    | 0    | 0    |
| 0    | 0    | 0    | 0    | \[FormalD][5] | 0    | 0    | 0    | 0    | 0    |⁠)
```

Define the "perfect shuffle" permutation:

```wl
In[3]:= perfectShuffle[n_Integer ? EvenQ] := PermutationMatrix[Flatten[Partition[Range[n], Quotient[n, 2]], {{2, 1}}]]
```

Use the perfect shuffle to transform the Jordan–Wielandt matrix into a tridiagonal matrix (a Golub–Kahan tridiagonal matrix):

```wl
In[4]:=
pm = perfectShuffle[Length[biblk]];
pm.biblk.Transpose[pm]//MatrixForm

Out[4]//MatrixForm=
(⁠|      |      |      |      |      |      |      |      |      |      |
| ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 0    | \[FormalD][1] | 0    | 0    | 0    | 0    | 0    | 0    | 0    | 0    |
| \[FormalD][1] | 0    | \[FormalE][1] | 0    |  ... | 0    | \[FormalD][4] | 0    | 0    |
| 0    | 0    | 0    | 0    | 0    | 0    | \[FormalD][4] | 0    | \[FormalE][4] | 0    |
| 0    | 0    | 0    | 0    | 0    | 0    | 0    | \[FormalE][4] | 0    | \[FormalD][5] |
| 0    | 0    | 0    | 0    | 0    | 0    | 0    | 0    | \[FormalD][5] | 0    |⁠)
```

Compute the singular values of a numerical upper bidiagonal matrix:

```wl
In[5]:= SingularValueList[bi2 = Normal[SparseArray[{Band[{1, 1}] -> {1., 3., 5., 7., 9., 11., 13.}, Band[{1, 2}] -> {2., 4., 6., 8., 10., 12.}}]]]

Out[5]= {20.4422, 14.7022, 10.4699, 7.11428, 4.40116, 2.23199, 0.6145}
```

These are equivalent to the positive eigenvalues of the Golub–Kahan tridiagonal matrix:

```wl
In[6]:= pm = perfectShuffle[2Length[bi2]];Select[Eigenvalues[pm.ArrayFlatten[{{0, Transpose[bi2]}, {bi2, 0}}].Transpose[pm]], Positive]

Out[6]= {20.4422, 14.7022, 10.4699, 7.11428, 4.40116, 2.23199, 0.6145}
```

## See Also

* [`Cycles`](https://reference.wolfram.com/language/ref/Cycles.en.md)
* [`PermutationCycles`](https://reference.wolfram.com/language/ref/PermutationCycles.en.md)
* [`PermutationList`](https://reference.wolfram.com/language/ref/PermutationList.en.md)
* [`Permute`](https://reference.wolfram.com/language/ref/Permute.en.md)
* [`LUDecomposition`](https://reference.wolfram.com/language/ref/LUDecomposition.en.md)
* [`QRDecomposition`](https://reference.wolfram.com/language/ref/QRDecomposition.en.md)

## Related Guides

* [Structured Arrays](https://reference.wolfram.com/language/guide/StructuredArrays.en.md)

## History

* [Introduced in 2022 (13.1)](https://reference.wolfram.com/language/guide/SummaryOfNewFeaturesIn131.en.md) \| [Updated in 2023 (13.3)](https://reference.wolfram.com/language/guide/SummaryOfNewFeaturesIn133.en.md) ▪ [2024 (14.0)](https://reference.wolfram.com/language/guide/SummaryOfNewFeaturesIn140.en.md)