In
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matric ...
, the permanent of a
square matrix
In mathematics, a square matrix is a matrix with the same number of rows and columns. An ''n''-by-''n'' matrix is known as a square matrix of order Any two square matrices of the same order can be added and multiplied.
Square matrices are ofte ...
is a function of the matrix similar to the
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 ...
. The permanent, as well as the determinant, is a polynomial in the entries of the matrix. Both are special cases of a more general function of a matrix called the
immanant.
Definition
The permanent of an matrix is defined as
The sum here extends over all elements σ of 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 ...
''S''
''n''; i.e. over all
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 p ...
s of the numbers 1, 2, ..., ''n''.
For example,
and
The definition of the permanent of ''A'' differs from that of the
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 ...
of ''A'' in that the
signatures of the permutations are not taken into account.
The permanent of a matrix A is denoted per ''A'', perm ''A'', or Per ''A'', sometimes with parentheses around the argument. Minc uses Per(''A'') for the permanent of rectangular matrices, and per(''A'') when ''A'' is a square matrix. Muir and Metzler use the notation
.
The word, ''permanent'', originated with Cauchy in 1812 as “fonctions symétriques permanentes” for a related type of function, and was used by Muir and Metzler in the modern, more specific, sense.
Properties
If one views the permanent as a map that takes ''n'' vectors as arguments, then it is a
multilinear map
In linear algebra, a multilinear map is a function of several variables that is linear separately in each variable. More precisely, a multilinear map is a function
:f\colon V_1 \times \cdots \times V_n \to W\text
where V_1,\ldots,V_n and W ar ...
and it is symmetric (meaning that any order of the vectors results in the same permanent). Furthermore, given a square matrix
of order ''n'':
* perm(''A'') is invariant under arbitrary permutations of the rows and/or columns of ''A''. This property may be written symbolically as perm(''A'') = perm(''PAQ'') for any appropriately sized
permutation matrices ''P'' and ''Q'',
* multiplying any single row or column of ''A'' by a
scalar ''s'' changes perm(''A'') to ''s''⋅perm(''A''),
* perm(''A'') is invariant under
transposition, that is, perm(''A'') = perm(''A''
T).
* If
and
are square matrices of order ''n'' then,
where ''s'' and ''t'' are subsets of the same size of and
are their respective complements in that set.
* If
is a
triangular matrix
In mathematics, a triangular matrix is a special kind of square matrix. A square matrix is called if all the entries ''above'' the main diagonal are zero. Similarly, a square matrix is called if all the entries ''below'' the main diagonal ar ...
, i.e.
, whenever
or, alternatively, whenever