In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, particularly in
matrix theory
In mathematics, a matrix (plural matrices) is a rectangular array or table of numbers, symbols, or expressions, arranged in rows and columns, which is used to represent a mathematical object or a property of such an object.
For example,
\begi ...
, a permutation matrix is a square
binary matrix
A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1) matrix is a matrix with entries from the Boolean domain Such a matrix can be used to represent a binary relation between a pair of finite sets.
Matrix representation ...
that has exactly one entry of 1 in each row and each column and 0s elsewhere. Each such matrix, say , represents a
permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
of elements and, when used to multiply another matrix, say , results in permuting the rows (when pre-multiplying, to form ) or columns (when post-multiplying, to form ) of the matrix .
Definition
Given a permutation of ''m'' elements,
:
represented in two-line form by
:
there are two natural ways to associate the permutation with a permutation matrix; namely, starting with the ''m'' × ''m''
identity matrix
In linear algebra, the identity matrix of size n is the n\times n square matrix with ones on the main diagonal and zeros elsewhere.
Terminology and notation
The identity matrix is often denoted by I_n, or simply by I if the size is immaterial o ...
, , either permute the columns or permute the rows, according to . Both methods of defining permutation matrices appear in the literature and the properties expressed in one representation can be easily converted to the other representation. This article will primarily deal with just one of these representations and the other will only be mentioned when there is a difference to be aware of.
The ''m × m'' permutation matrix ''P''
= (''p''
''ij'') obtained by permuting the columns of the identity matrix , that is, for each ''i'', if ''j'' = (''i'') and otherwise, will be referred to as the column representation in this article. Since the entries in row ''i'' are all 0 except that a 1 appears in column (''i''), we may write
:
where
, a standard basis vector, denotes a row vector of length ''m'' with 1 in the ''j''th position and 0 in every other position.
[Brualdi (2006) p.2]
For example, the permutation matrix ''P''
corresponding to the permutation
is
:
Observe that the ''j''th column of the identity matrix now appears as the (''j'')th column of ''P''
.
The other representation, obtained by permuting the rows of the identity matrix , that is, for each ''j'', ''p''
''ij'' = 1 if ''i'' = (''j'') and otherwise, will be referred to as the row representation.
Properties
The column representation of a permutation matrix is used throughout this section, except when otherwise indicated.
Multiplying
times a
column vector
In linear algebra, a column vector with m elements is an m \times 1 matrix consisting of a single column of m entries, for example,
\boldsymbol = \begin x_1 \\ x_2 \\ \vdots \\ x_m \end.
Similarly, a row vector is a 1 \times n matrix for some n, c ...
g will permute the rows of the vector:
Repeated use of this result shows that if is an appropriately sized matrix, the product,
is just a permutation of the rows of . However, observing that
for each shows that the permutation of the rows is given by
−1. (
is the
transpose
In linear algebra, the transpose of a matrix is an operator which flips a matrix over its diagonal;
that is, it switches the row and column indices of the matrix by producing another matrix, often denoted by (among other notations).
The tr ...
of matrix .)
As permutation matrices are
orthogonal matrices
In linear algebra, an orthogonal matrix, or orthonormal matrix, is a real square matrix whose columns and rows are orthonormal vectors.
One way to express this is
Q^\mathrm Q = Q Q^\mathrm = I,
where is the transpose of and is the identity ma ...
(that is,
), the inverse matrix exists and can be written as
Multiplying a
row vector
In linear algebra, a column vector with m elements is an m \times 1 matrix consisting of a single column of m entries, for example,
\boldsymbol = \begin x_1 \\ x_2 \\ \vdots \\ x_m \end.
Similarly, a row vector is a 1 \times n matrix for some n, c ...
h times
will permute the columns of the vector:
Again, repeated application of this result shows that post-multiplying a matrix by the permutation matrix , that is, , results in permuting the columns of . Notice also that
Given two permutations and of elements, the corresponding permutation matrices and acting on column vectors are composed with
The same matrices acting on row vectors (that is, post-multiplication) compose according to the same rule
To be clear, the above formulas use the
prefix notation
Polish notation (PN), also known as normal Polish notation (NPN), Łukasiewicz notation, Warsaw notation, Polish prefix notation or simply prefix notation, is a mathematical notation in which operators ''precede'' their operands, in contrast t ...
for permutation composition, that is,
Let
be the permutation matrix corresponding to in its row representation. The properties of this representation can be determined from those of the column representation since
In particular,
From this it follows that
Similarly,
Permutation matrices can be
characterized as the
orthogonal matrices
In linear algebra, an orthogonal matrix, or orthonormal matrix, is a real square matrix whose columns and rows are orthonormal vectors.
One way to express this is
Q^\mathrm Q = Q Q^\mathrm = I,
where is the transpose of and is the identity ma ...
whose entries are all
non-negative
In mathematics, the sign of a real number is its property of being either positive, negative, or zero. Depending on local conventions, zero may be considered as being neither positive nor negative (having no sign or a unique third sign), or it ...
.
Matrix group
If (1) denotes the identity permutation, then is the
identity matrix
In linear algebra, the identity matrix of size n is the n\times n square matrix with ones on the main diagonal and zeros elsewhere.
Terminology and notation
The identity matrix is often denoted by I_n, or simply by I if the size is immaterial o ...
.
Let denote the
symmetric group
In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group \m ...
, or
group of permutations, on . Since there are permutations, there are permutation matrices. By the formulas above, the permutation matrices form a
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
under matrix multiplication with the identity matrix as the
identity element
In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
.
The map that sends a permutation to its column representation is a
faithful representation In mathematics, especially in an area of abstract algebra known as representation theory, a faithful representation ρ of a group on a vector space is a linear representation in which different elements of are represented by distinct linear mapp ...
.
Doubly stochastic matrices
A permutation matrix is itself a
doubly stochastic matrix In mathematics, especially in probability and combinatorics, a doubly stochastic matrix
(also called bistochastic matrix) is a square matrix X=(x_) of nonnegative real numbers, each of whose rows and columns sums to 1, i.e.,
:\sum_i x_=\sum_j x_=1 ...
, but it also plays a special role in the theory of these matrices. The
Birkhoff–von Neumann theorem In mathematics, especially in probability and combinatorics, a doubly stochastic matrix
(also called bistochastic matrix) is a square matrix X=(x_) of nonnegative real numbers, each of whose rows and columns sums to 1, i.e.,
:\sum_i x_=\sum_j x_=1 ...
says that every doubly stochastic real matrix is a
convex combination
In convex geometry and vector algebra, a convex combination is a linear combination of points (which can be vectors, scalars, or more generally points in an affine space) where all coefficients are non-negative and sum to 1. In other word ...
of permutation matrices of the same order and the permutation matrices are precisely the
extreme point
In mathematics, an extreme point of a convex set S in a real or complex vector space is a point in S which does not lie in any open line segment joining two points of S. In linear programming problems, an extreme point is also called vertex or ...
s of the set of doubly stochastic matrices. That is, the
Birkhoff polytope
The Birkhoff polytope ''B'n'' (also called the assignment polytope, the polytope of doubly stochastic matrices, or the perfect matching polytope of the complete bipartite graph K_) is the convex polytope in R''N'' (where ''N'' = ''n''2) who ...
, the set of doubly stochastic matrices, is the
convex hull
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
of the set of permutation matrices.
[Brualdi (2006) p.19]
Linear algebraic properties
The
trace
Trace may refer to:
Arts and entertainment Music
* ''Trace'' (Son Volt album), 1995
* ''Trace'' (Died Pretty album), 1993
* Trace (band), a Dutch progressive rock band
* ''The Trace'' (album)
Other uses in arts and entertainment
* ''Trace'' ...
of a permutation matrix is the number of
fixed points of the permutation. If the permutation has fixed points, so it can be written in cycle form as where has no fixed points, then are
eigenvector
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...
s of the permutation matrix.
To calculate the
eigenvalue
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...
s of a permutation matrix
, write
as a product of
cycles, say,
. Let the corresponding lengths of these cycles be
, and let
be the set of complex solutions of
. The union of all
s is the set of eigenvalues of the corresponding permutation matrix. The
geometric multiplicity
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted ...
of each eigenvalue equals the number of
s that contain it.
[J Najnudel, A Nikeghbali 2010 p.4]
From
group theory
In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...
we know that any permutation may be written as a product of
transpositions. Therefore, any permutation matrix factors as a product of row-interchanging
elementary matrices, each having
determinant
In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and ...
−1. Thus, the determinant of a permutation matrix is the
signature
A signature (; from la, signare, "to sign") is a handwritten (and often stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and intent. The writer of a ...
of the corresponding permutation.
Examples
Permutation of rows and columns
When a matrix ''M'' is multiplied by a permutation matrix ''P'' on the left to make ''PM'', the product is the result of permuting the rows of ''M''. As a special case, if ''M'' is a column vector, then ''PM'' is the result of permuting the entries of ''M'':
When instead ''M'' is multiplied by a permutation matrix on the right to make ''MP'', the product is the result of permuting the columns of ''M''. As a special case, if ''M'' is a row vector, then ''MP'' is the result of permuting the entries of ''M'':
Permutation of rows
The permutation matrix ''P''
π corresponding to the permutation
is
:
Given a vector g,
:
Explanation
A permutation matrix will always be in the form
:
where e
''a''''i'' represents the ''i''th basis vector (as a row) for R
''j'', and where
:
is the
permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
form of the permutation matrix.
Now, in performing
matrix multiplication
In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the s ...
, one essentially forms the
dot product
In mathematics, the dot product or scalar productThe term ''scalar product'' means literally "product with a scalar as a result". It is also used sometimes for other symmetric bilinear forms, for example in a pseudo-Euclidean space. is an algebra ...
of each row of the first matrix with each column of the second. In this instance, we will be forming the dot product of each row of this matrix with the vector of elements we want to permute. That is, for example, v = (''g''
0,...,''g''
5)
T,
:e
''a''''i''·v = ''g''
''a''''i''
So, the product of the permutation matrix with the vector v above, will be a vector in the form (''g''
''a''1, ''g''
''a''2, ..., ''g''
''a''''j''), and that this then is a permutation of v since we have said that the permutation form is
:
So, permutation matrices do indeed permute the order of elements in vectors multiplied with them.
Restricted forms
*
Costas array
In mathematics, a Costas array can be regarded geometrically as a set of ''n'' points, each at the center of a square in an ''n''×''n'' square tiling such that each row or column contains only one point, and all of the ''n''(''n'' &minu ...
, a permutation matrix in which the displacement vectors between the entries are all distinct
*
n-queens puzzle, a permutation matrix in which there is at most one entry in each diagonal and antidiagonal
See also
*
Alternating sign matrix
*
Exchange matrix In mathematics, especially linear algebra, the exchange matrices (also called the reversal matrix, backward identity, or standard involutory permutation) are special cases of permutation matrix, permutation matrices, where the 1 elements reside on t ...
*
Generalized permutation matrix
In mathematics, a generalized permutation matrix (or monomial matrix) is a matrix with the same nonzero pattern as a permutation matrix, i.e. there is exactly one nonzero entry in each row and each column. Unlike a permutation matrix, where the no ...
*
Rook polynomial
In combinatorial mathematics, a rook polynomial is a generating polynomial of the number of ways to place non-attacking rooks on a board that looks like a checkerboard; that is, no two rooks may be in the same row or column. The board is any sub ...
*
Permanent
Permanent may refer to:
Art and entertainment
* ''Permanent'' (film), a 2017 American film
* ''Permanent'' (Joy Division album)
* "Permanent" (song), by David Cook
Other uses
* Permanent (mathematics), a concept in linear algebra
* Permanent (cy ...
References
*
*
{{Authority control
Matrices
Permutations
Sparse matrices