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

  • 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 , the resulting permutation matrix is given by P〚i,j〛=TemplateBox[{{i, ,, {p, _, j}}}, KroneckerDeltaSeq]. This corresponds to a matrix that has a one in column of row and zeros elsewhere.
  • A permutation matrix can be used to permute rows by multiplying from the left or permute columns by multiplying its transpose from the right A.TemplateBox[{P}, Transpose].
  • A permutation matrix is an orthogonal matrix, where the inverse is equivalent to the transpose P^(-1)=TemplateBox[{P}, Transpose].
  • Permutation matrices are closed under matrix multiplication, so is again a permutation matrix.
  • The determinant of a permutation matrix is either or 1 and equals Signature[permv].
  • Operations that are accelerated for PermutationMatrix include:
  • Dettime
    Dottime
    Inversetime
    LinearSolvetime
  • The option WorkingPrecision can be used to specify the precision of matrix elements.
  • 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.

Examples

open allclose all

Basic Examples  (2)

Construct a permutation matrix from a permutation vector:

Show the elements:

Get the normal representation:

Represent a permutation matrix as a structured array:

Show the elements:

Compute the determinant:

Scope  (7)

Construct a permutation matrix from a disjoint cycle representation:

Show the elements:

Get the normal representation:

Specify the dimension of the permutation matrix:

Show the elements:

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

Show the elements:

Get the normal representation:

Specify the dimension of the permutation matrix:

Show the elements:

Construct a permutation matrix from an explicit matrix:

Show the elements:

Get the normal representation:

PermutationMatrix objects include properties that give information about the array:

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

"PermutationList" gives the permutation list representation:

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

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

Structured algorithms are typically faster:

Compute the determinant:

Compute the inverse:

Compute the eigenvalues:

When appropriate, structured algorithms return another PermutationMatrix object:

The inverse allows you to easily get the inverse permutation:

Verify the inverse relationship:

This is equivalent to the result of InversePermutation:

Generate a random 104×104 permutation matrix:

The representation and computation are efficient for the structured array:

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

The inverse needs 2.4 GB of storage:

Options  (1)

WorkingPrecision  (1)

Specify the working precision for the permutation matrix:

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

Applications  (3)

A function for computing the LU decomposition of a matrix:

Compute the decomposition:

Verify the decomposition:

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

Compute a multiplication table for the group:

This is equivalent to the result of GroupMultiplicationTable:

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:

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

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

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

The result is equivalent to applying Fourier to the vector:

Properties & Relations  (5)

Convert an identity matrix to a permutation matrix:

Show the disjoint cycle representation:

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

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

Generate a random permutation list:

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

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

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

Neat Examples  (1)

An upper bidiagonal matrix:

Generate a symmetric block matrix with bidiagonal blocks (a JordanWielandt matrix):

Define the "perfect shuffle" permutation:

Use the perfect shuffle to transform the JordanWielandt matrix into a tridiagonal matrix (a GolubKahan tridiagonal matrix):

Compute the singular values of a numerical upper bidiagonal matrix:

These are equivalent to the positive eigenvalues of the GolubKahan tridiagonal matrix:

Wolfram Research (2022), PermutationMatrix, Wolfram Language function, https://reference.wolfram.com/language/ref/PermutationMatrix.html.

Text

Wolfram Research (2022), PermutationMatrix, Wolfram Language function, https://reference.wolfram.com/language/ref/PermutationMatrix.html.

CMS

Wolfram Language. 2022. "PermutationMatrix." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/PermutationMatrix.html.

APA

Wolfram Language. (2022). PermutationMatrix. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/PermutationMatrix.html

BibTeX

@misc{reference.wolfram_2022_permutationmatrix, author="Wolfram Research", title="{PermutationMatrix}", year="2022", howpublished="\url{https://reference.wolfram.com/language/ref/PermutationMatrix.html}", note=[Accessed: 09-August-2022 ]}

BibLaTeX

@online{reference.wolfram_2022_permutationmatrix, organization={Wolfram Research}, title={PermutationMatrix}, year={2022}, url={https://reference.wolfram.com/language/ref/PermutationMatrix.html}, note=[Accessed: 09-August-2022 ]}