Permutation matrices

The pMatrix class is the class of permutation matrices, stored as 1-based integer permutation vectors. A permutation matrix is a square matrix whose rows and columns are all standard unit vectors. It follows that permutation matrices are a special case of index matrices (hence pMatrix is defined as a direct subclass of indMatrix).

Multiplying a matrix on the left by a permutation matrix is equivalent to permuting its rows. Analogously, multiplying a matrix on the right by a permutation matrix is equivalent to permuting its columns. Indeed, such products are implemented in Matrix as indexing operations; see ‘Details’ below.

Objects from the Class

Objects can be created explicitly with calls of the form new("pMatrix", ...), but they are more commonly created by coercing 1-based integer index vectors, with calls of the form as(., "pMatrix"); see ‘Methods’ below.

Slots

margin,perm

inherited from superclass indMatrix. Here, perm is an integer vector of length Dim[1] and a permutation of 1:Dim[1].

Dim,Dimnames

inherited from virtual superclass Matrix.

Extends

Class "indMatrix", directly.

Methods

%*%

signature(x = "pMatrix", y = "Matrix") and others listed by showMethods("%*%", classes = "pMatrix"): matrix products implemented where appropriate as indexing operations.

coerce

signature(from = "numeric", to = "pMatrix"): supporting typical pMatrix construction from a vector of positive integers, specifically a permutation of 1:n. Row permutation is assumed.

t

signature(x = "pMatrix"): the transpose, which is a pMatrix with identical perm but opposite margin. Coincides with the inverse, as permutation matrices are orthogonal.

solve

signature(a = "pMatrix", b = "missing"): the inverse permutation matrix, which is a pMatrix with identical perm but opposite margin. Coincides with the transpose, as permutation matrices are orthogonal. See showMethods("solve", classes = "pMatrix") for more signatures.

determinant

signature(x = "pMatrix", logarithm = "logical"): always returning 1 or -1, as permutation matrices are orthogonal. In fact, the result is exactly the sign of the permutation.

Details

By definition, a permutation matrix is both a row index matrix and a column index matrix. However, the perm slot of a pMatrix cannot be used interchangeably as a row index vector and column index vector. If margin=1, then perm is a row index vector, and the corresponding column index vector can be computed as invPerm(perm), i.e., by inverting the permutation. Analogously, if margin=2, then perm and invPerm(perm) are column and row index vectors, respectively.

Given an n-by-n row permutation matrix P with perm slot p and a matrix M with conformable dimensions, we have

\(P M\)	=	P %*% M	=	M[p, ]
\(M P\)	=	M %*% P	=	M[, i(p)]
\(P'M\)	=	crossprod(P, M)	=	M[i(p), ]
\(MP'\)	=	tcrossprod(M, P)	=	M[, p]
\(P'P\)	=	crossprod(P)	=	Diagonal(n)
\(PP'\)	=	tcrossprod(P)	=	Diagonal(n)

where i := invPerm.

See also

Superclass indMatrix of index matrices, for many inherited methods; invPerm, for computing inverse permutation vectors.

Examples

(pm1 <- as(as.integer(c(2,3,1)), "pMatrix"))
#> 3 x 3 sparse Matrix of class "pMatrix"
#>           
#> [1,] . | .
#> [2,] . . |
#> [3,] | . .
t(pm1) # is the same as
#> 3 x 3 sparse Matrix of class "pMatrix"
#>           
#> [1,] . . |
#> [2,] | . .
#> [3,] . | .
solve(pm1)
#> 3 x 3 sparse Matrix of class "pMatrix"
#>           
#> [1,] . . |
#> [2,] | . .
#> [3,] . | .
pm1 %*% t(pm1) # check that the transpose is the inverse
#> 3 x 3 sparse Matrix of class "pMatrix"
#>           
#> [1,] | . .
#> [2,] . | .
#> [3,] . . |
stopifnot(all(diag(3) == as(pm1 %*% t(pm1), "matrix")),
          is.logical(as(pm1, "matrix")))

set.seed(11)
## random permutation matrix :
(p10 <- as(sample(10),"pMatrix"))
#> 10 x 10 sparse Matrix of class "pMatrix"
#>                          
#>  [1,] . . . . . . . . . |
#>  [2,] . | . . . . . . . .
#>  [3,] . . . . . . . | . .
#>  [4,] | . . . . . . . . .
#>  [5,] . . . . . . | . . .
#>  [6,] . . . . | . . . . .
#>  [7,] . . . | . . . . . .
#>  [8,] . . . . . . . . | .
#>  [9,] . . | . . . . . . .
#> [10,] . . . . . | . . . .

## Permute rows / columns of a numeric matrix :
(mm <- round(array(rnorm(3 * 3), c(3, 3)), 2))
#>       [,1]  [,2]  [,3]
#> [1,] -0.15 -0.44 -0.38
#> [2,]  1.04 -0.05 -0.04
#> [3,]  0.19  0.47 -2.14
mm %*% pm1
#> 3 x 3 Matrix of class "dgeMatrix"
#>       [,1]  [,2]  [,3]
#> [1,] -0.38 -0.15 -0.44
#> [2,] -0.04  1.04 -0.05
#> [3,] -2.14  0.19  0.47
pm1 %*% mm
#> 3 x 3 Matrix of class "dgeMatrix"
#>       [,1]  [,2]  [,3]
#> [1,]  1.04 -0.05 -0.04
#> [2,]  0.19  0.47 -2.14
#> [3,] -0.15 -0.44 -0.38
try(as(as.integer(c(3,3,1)), "pMatrix"))# Error: not a permutation
#> Error in .perm2ind(from, check.p = 2L) : 
#>   'perm' is not a permutation of seq_len(max(perm, 0))

as(pm1, "TsparseMatrix")
#> 3 x 3 sparse Matrix of class "ngTMatrix"
#>           
#> [1,] . | .
#> [2,] . . |
#> [3,] | . .
p10[1:7, 1:4] # gives an "ngTMatrix" (most economic!)
#> 7 x 4 sparse Matrix of class "ngCMatrix"
#>             
#> [1,] . . . .
#> [2,] . | . .
#> [3,] . . . .
#> [4,] | . . .
#> [5,] . . . .
#> [6,] . . . .
#> [7,] . . . |

## row-indexing of a <pMatrix> keeps it as an <indMatrix>:
p10[1:3, ]
#> 3 x 10 sparse Matrix of class "indMatrix"
#>                         
#> [1,] . . . . . . . . . |
#> [2,] . | . . . . . . . .
#> [3,] . . . . . . . | . .