Class PermutationMatrix

java.lang.Object
org.flag4j.arrays.sparse.PermutationMatrix
All Implemented Interfaces:
Serializable
public class PermutationMatrix extends Object implements Serializable

Represents a square permutation matrix with rows and columns equal to size, where each row and column contains exactly one entry of 1, and all other entries are 0. Internally, this class stores a permutation array so that permutation[i] = j indicates that there is a 1 at row i, column j.

Permutation matrices are orthogonal (and unitary in the complex case), so their inverse is equal to their transpose.

Permutation matrices are useful for permuting rows or columns of another matrix.

  • Left multiplying another matrix by a permutation matrix permutes the rows of that matrix.
  • Right multiplying another matrix by a permutation matrix permutes the columns of that matrix.

The determinant of any permutation matrix is always +1 or -1, depending on the parity of the permutation (i.e. the number of swaps in the matrix).

The identity matrix is a special case of a permutation matrix, corresponding to the identity permutation {0, 1, ..., n-1}.

Example usage:


         // Construct matrices to permute.
         Matrix a = new Vector(ArrayUtils.range(0, 5)).repeat(5, 1);
         Matrix b = a.T();

         // Create matrix to permute rows according to (4, 2, 3, 0, 1)
         PermutationMatrix p1 = new PermutationMatrix(4, 2, 3, 0, 1);

         // Permute rows of a according to (0, 1, 2, 3, 4) -> (4, 2, 3, 0, 1)
         Matrix aPerm = p1.leftMult(a);

         // Permute columns of b according to (0, 1, 2, 3, 4) -> (4, 2, 3, 0, 1)
         Matrix bPerm = p1.T().rightMult(b);

         // Display original matrices are their permuted counterparts.
         System.out.println("a:\n" + a + "\naPerm:\n" + aPerm + "\n");
         System.out.println("b:\n" + b + "\nbPerm:\n" + bPerm);
See Also:

  • Field Details

    • permutation

      protected final int[] permutation
      Describes the permutation represented by this permutation matrix. permutation[i] = j indicates that there is a 1 at row i, column j with in permutation matrix.

    • size

      public final int size
      Size of this permutation matrix.

    • shape

      public final Shape shape
      Shape of this permutation matrix.

  • Constructor Details

    • PermutationMatrix

      public PermutationMatrix(int size)
      Creates a permutation matrix which is equivalent to the identity matrix of the specified size.
      Parameters:
      size - Size of the permutation matrix. That is, the number of rows and columns

    • PermutationMatrix

      public PermutationMatrix(Shape shape)
      Creates a permutation matrix which is equivalent to the identity matrix of the specified size.
      Parameters:
      shape - Shape of the permutation matrix. That is, the number of rows and columns. Must be a square shape.
      Throws:
      LinearAlgebraException - If shape is not square.

    • PermutationMatrix

      public PermutationMatrix(PermutationMatrix src)
      Copy constructor which creates a deep copy of the src permutation matrix.
      Parameters:
      src - The permutation matrix to copy.

    • PermutationMatrix

      public PermutationMatrix(int... permutation)

      Constructs a permutation matrix from the specified permutation.

      This constructor will explicitly verify that permutation is a valid permutation. It is highly recommended to do this. However, there is a

      Parameters:
      permutation - Array specifying the permutation. Must contain a permutation of {0, 1, ..., permutation.length-1}. permutation[i] = j indicates that there is a 1 at row i, column j.
      Throws:
      IllegalArgumentException - permutation is not a permutation of
      invalid @code 
      {@code {0, 1, ..., permutation.length-1}.

    • PermutationMatrix

      public PermutationMatrix(int[] permutation, boolean ensurePermutation)

      Constructs a permutation matrix from the specified permutation. This constructor also accepts a flag indicating if an explicit check should be made to enforce that the permutation array is a valid permutation.

      It is highly recommended to use PermutationMatrix(int[]) or set ensurePermutation = true. However, if there is absolute confidence in the validity of the permutation array, then setting ensurePermutation = false may yield very slight performance benefits.

      Parameters:
      permutation - Array specifying the permutation. Must contain a permutation of {0, 1, ..., permutation.length-1}. permutation[i] = j indicates that there is a 1 at row i, column j.
      ensurePermutation - Flag indicating if an explicit check should be made to verify that permutation is a valid permutation of {0, 1, ..., permutation.length-1}.
      • If true: an explicit check will be made that permutation is a valid permutation.
      • If false: NO check will be made to ensure permutation is a valid permutation.
      Throws:
      IllegalArgumentException - If ensurePermutation == true and permutation is not a permutation of
      invalid @code 
      {@code {0, 1, ..., permutation.length-1}.

  • Method Details

    • getPermutation

      public int[] getPermutation()
      Returns the permutation represented by this permutation matrix.
      Returns:
      The permutation represented by this permutation matrix.

    • fromColSwaps

      public static PermutationMatrix fromColSwaps(int[] colPermutation)
      Creates a permutation matrix with the specified column permutation. That is, a permutation matrix such that right multiplying it with another matrix results in permuting th columns of that matrix according to colPermutation.
      Parameters:
      colPermutation - Array specifying column permutation. The entry x at index i indicates that column i has been swapped with column x. permutation array.
      Returns:
      A permutation matrix that when right multiplied to a matrix results in permuting the columns of that matrix according to colPermutation.
      Throws:
      IllegalArgumentException - If colPermutation is not a valid permutation.

    • copy

      public PermutationMatrix copy()
      Creates a copy of this permutation matrix.
      Returns:
      A copy of this permutation matrix.

    • equals

      public boolean equals(Object object)
      Checks if this permutation matrix is equal to the given object. A permutation matrix is considered equal to an object if that object is also a permutation matrix and represents the same matrix.
      Overrides:
      equals in class Object
      Parameters:
      object - Object to compare to this permutation matrix.
      Returns:
      True if b is a permutation matrix and equivalent to this matrix (in terms of matrix equality).

    • hashCode

      public int hashCode()
      Returns a hashcode for this permutation matrix by calling Arrays.hashCode(permutation).
      Overrides:
      hashCode in class Object
      Returns:
      The hashcode for this permutation matrix.

    • mult

      public PermutationMatrix mult(PermutationMatrix b)
      Computes the matrix-matrix multiplication between two permutation matrices.
      Parameters:
      b - The matrix to multiply to this permutation matrix.
      Returns:
      The matrix=matrix product of this permutation matrix with b.
      Throws:
      TensorShapeException - If this.size != b.size.

    • leftMult

      public Matrix leftMult(Matrix src)
      Left multiplies this permutation matrix to the specified matrix. This will have the effect of swapping rows in the src matrix.
      Parameters:
      src - The matrix to left multiply this permutation matrix to.
      Returns:
      The result of left multiplying this permutation matrix to the src matrix.
      Throws:
      IllegalArgumentException - If the number of rows in src does not equal the size of this permutation matrix.
      See Also:

    • leftMult

      public Vector leftMult(Vector src)
      Left multiplies this permutation matrix to the specified vector. This will have the effect of swapping rows in the src vector. The vector will be treated as a column vector.
      Parameters:
      src - The vector to left multiply this permutation matrix to.
      Returns:
      The result of left multiplying this permutation matrix to the src vector.
      Throws:
      IllegalArgumentException - If size of src does not equal the size of this permutation matrix.
      See Also:

    • leftMult

      public CMatrix leftMult(CMatrix src)
      Left multiplies this permutation matrix to the specified matrix. This will have the effect of swapping rows in the src matrix.
      Parameters:
      src - The matrix to left multiply this permutation matrix to.
      Returns:
      The result of left multiplying this permutation matrix to the src matrix.
      Throws:
      IllegalArgumentException - If the number of rows in src does not equal the size of this permutation matrix.
      See Also:

    • leftMult

      public CVector leftMult(CVector src)
      Left multiplies this permutation matrix to the specified vector. This will have the effect of swapping rows in the src vector. The vector will be treated as a column vector.
      Parameters:
      src - The vector to left multiply this permutation matrix to.
      Returns:
      The result of left multiplying this permutation matrix to the src vector.
      Throws:
      IllegalArgumentException - If size of src does not equal the size of this permutation matrix.
      See Also:

    • rightMult

      public Matrix rightMult(Matrix src)
      Right multiplies this permutation matrix to the specified matrix. This is equivalent to swapping columns in the src matrix.
      Parameters:
      src - The matrix to right multiply this permutation matrix to.
      Returns:
      The result of right multiplying this permutation matrix to the src matrix.
      Throws:
      IllegalArgumentException - If the number of columns in src does not match the size of this permutation matrix.
      See Also:

    • rightMult

      public Vector rightMult(Vector src)
      Right multiplies this permutation matrix to the specified vector. This will have the effect of swapping columns in the src vector. The vector will be treated as a row vector.
      Parameters:
      src - The vector to right multiply this permutation matrix to.
      Returns:
      The result of right multiplying this permutation matrix to the src vector.
      Throws:
      IllegalArgumentException - If size of src does not equal the size of this permutation matrix.
      See Also:

    • rightMult

      public CMatrix rightMult(CMatrix src)
      Right multiplies this permutation matrix to the specified matrix. This is equivalent to swapping columns in the src matrix.
      Parameters:
      src - The matrix to right multiply this permutation matrix to.
      Returns:
      The result of right multiplying this permutation matrix to the src matrix.
      Throws:
      IllegalArgumentException - If the number of columns in src does not match the size of this permutation matrix.
      See Also:

    • rightMult

      public CVector rightMult(CVector src)
      Right multiplies this permutation matrix to the specified vector. This will have the effect of swapping columns in the src vector. The vector will be treated as a row vector.
      Parameters:
      src - The vector to right multiply this permutation matrix to.
      Returns:
      The result of right multiplying this permutation matrix to the src vector.
      Throws:
      IllegalArgumentException - If size of src does not equal the size of this permutation matrix.
      See Also:

    • swapRows

      public void swapRows(int row1, int row2)
      Swaps two rows in this permutation matrix.
      Parameters:
      row1 - First row to swap in the permutation matrix.
      row2 - Second row to swap in the permutation matrix.
      Throws:
      ArrayIndexOutOfBoundsException - If either row1 or row2 is out of bounds of this permutation matrix.

    • swapCols

      public void swapCols(int col1, int col2)
      Swaps two columns in this permutation matrix.
      Parameters:
      col1 - First column to swap in the permutation matrix.
      col2 - Second column to swap in the permutation matrix.
      Throws:
      ArrayIndexOutOfBoundsException - If either col1 or col2 is out of bounds of this permutation matrix.

    • permuteRows

      public void permuteRows(int[] swaps)
      Permutes rows of this permutation matrix.
      Parameters:
      swaps - Defines row swaps of this permutation matrix. The entry x at index i represents row i has been swapped with row x. This must be a permutation array.
      Throws:
      IllegalArgumentException - If swaps is not the same length as the number of rows/columns in this permutation matrix. Or, if swaps is not a permutation array.

    • inv

      public PermutationMatrix inv()
      Computes the inverse/transpose of this permutation matrix.
      Returns:
      The inverse/transpose of this permutation matrix.

    • T

      public PermutationMatrix T()
      Computes the transpose/inverse of this permutation matrix.
      Returns:
      The transpose/inverse of this permutation matrix.

    • trace

      public int trace()
      Computes the trace of this permutation matrix.
      Returns:
      The trace of this permutation matrix.

    • tr

      public int tr()
      Computes the trace of this permutation matrix. Alias for trace().
      Returns:
      The trace of this permutation matrix.

    • computeSwaps

      public int computeSwaps()
      Computes the number of row/column swaps required for this permutation matrix to be converted to the identity matrix.
      Returns:
      The total number of row/column swaps required to convert this permutation matrix to the identity matrix.

    • det

      public int det()
      Computes the determinant of this permutation matrix (will be +/- 1).
      Returns:
      The determinant of this permutation matrix (will be +/- 1).

    • toDense

      public Matrix toDense()
      Converts this permutation matrix to a real dense matrix.
      Returns:
      A real dense matrix which is equivalent to this permutation matrix.
      See Also:

    • toCoo

      public CooMatrix toCoo()
      Converts this permutation matrix to a real sparse COO matrix.
      Returns:
      real sparse COO matrix which is equivalent to this permutation matrix.
      See Also:

    • toCsr

      public CsrMatrix toCsr()
      Converts this permutation matrix to a real sparse COO matrix.
      Returns:
      real sparse COO matrix which is equivalent to this permutation matrix
      See Also:

    • toString

      public String toString()
      Converts this permutation matrix to a human-readable string.
      Overrides:
      toString in class Object
      Returns:
      This permutation matrix represented as a human-readable string.