In
linear algebraLinear algebra is a branch of mathematics concerned with the study of vectors, vector spaces , linear maps , and systems of linear equations. Vector spaces are a central theme in modern mathematics; thus, linear algebra is widely used in both abstract algebra and functional analysis...
, the
permanent of a square matrix is a function of the matrix similar to the
determinantIn algebra, the determinant is a special number associated to any square matrix, that is to say, a rectangular array of numbers where the number of rows and columns are equal. The fundamental geometric meaning of a determinant is a scale factor for measure when the matrix is regarded as a linear...
. The permanent, as well as the determinant, is a polynomial in the entries of the matrix. Both permanent and determinant are special cases of a more general function of a matrix called the immanant.
The permanent of an
n-by-
n matrix
A = (
ai,j) is defined as
The sum here extends over all elements σ of the
symmetric groupIn mathematics, the symmetric group on a set is the group consisting of all automorphisms of the set with function composition as the group operation....
Sn, i.e.
In
linear algebraLinear algebra is a branch of mathematics concerned with the study of vectors, vector spaces , linear maps , and systems of linear equations. Vector spaces are a central theme in modern mathematics; thus, linear algebra is widely used in both abstract algebra and functional analysis...
, the
permanent of a square matrix is a function of the matrix similar to the
determinantIn algebra, the determinant is a special number associated to any square matrix, that is to say, a rectangular array of numbers where the number of rows and columns are equal. The fundamental geometric meaning of a determinant is a scale factor for measure when the matrix is regarded as a linear...
. The permanent, as well as the determinant, is a polynomial in the entries of the matrix. Both permanent and determinant are special cases of a more general function of a matrix called the immanant.
Definition
The permanent of an
n-by-
n matrix
A = (
ai,j) is defined as
The sum here extends over all elements σ of the
symmetric groupIn mathematics, the symmetric group on a set is the group consisting of all automorphisms of the set with function composition as the group operation....
Sn, i.e. over all
permutationIn several fields of mathematics the term permutation is used with different but closely related meanings. They all relate to the notion of mapping the elements of a set to other elements of the same set, i.e., exchanging elements of a set.- Definitions :The general concept of permutation can be...
s of the numbers 1, 2, ...,
n.
For example,
The definition of the permanent of
A differs from that of the
determinantIn algebra, the determinant is a special number associated to any square matrix, that is to say, a rectangular array of numbers where the number of rows and columns are equal. The fundamental geometric meaning of a determinant is a scale factor for measure when the matrix is regarded as a linear...
of
A in that the signatures of the permutations are not taken into account. If one views the permanent as a map that takes
n vectors as arguments, then it is a
multilinear mapIn linear algebra, a multilinear map is a mathematical function of several vector variables that is linear in each variable.A multilinear map of n variables is also called an n-linear map....
and it is symmetric (meaning that any order of the vectors results in the same permanent). A formula similar to Laplace's for the development of a determinant along a row or column is also valid for the permanent; all signs have to be ignored for the permanent.
Properties and applications
Unlike the determinant, the permanent has no easy geometrical interpretation; it is mainly used in
combinatoricsCombinatorics is a branch of pure mathematics concerning the study of discrete objects. It is related to many other areas of mathematics, such as algebra, probability theory, ergodic theory and geometry, as well as to applied subjects in computer science and statistical physics...
and in treating boson Green's functions in
quantum field theoryQuantum field theory provides a theoretical framework for constructing quantum mechanical models of systems classically described by fields or of many-body systems. It is widely used in particle physics and condensed matter physics...
. However, it has two graph-theoretic interpretations: as the sum of weights of
cycle coverIn graph theory and combinatorial optimization, cycle cover may have the following meanings*Vertex cycle cover*Vertex disjoint cycle cover*Edge cycle cover...
s of a
directed graphA directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,* a set A of ordered pairs of vertices, called arcs, directed edges, or arrows .It differs from an ordinary or undirected graph, in that the latter is defined in terms of unordered pairs of...
, and as the sum of weights of perfect matchings in a
bipartite graphIn the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
.
Cycle covers
Any square matrix can be viewed as the
adjacency matrixIn mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
of a directed graph, with representing the weight of the edge from vertex
i to vertex
j.
A
cycle coverIn mathematics, a vertex cycle cover of a graph is the set of cycles which are subgraphs of G and contain all vertices of G....
of a weighted directed graph is a collection of vertex-disjoint directed cycles in the graph that covers all nodes in the graph. Thus, each vertex
i in the graph has a unique "successor" in the cycle cover, and is a
permutationIn several fields of mathematics the term permutation is used with different but closely related meanings. They all relate to the notion of mapping the elements of a set to other elements of the same set, i.e., exchanging elements of a set.- Definitions :The general concept of permutation can be...
on where
n is the number of vertices in the graph. Conversely, any permutation on corresponds to a cycle cover in which there is an edge from vertex
i to vertex for each
i.
If the weight of a cycle-cover is defined to be the product of the weights of the edges in each cycle, then
The permanent of an matrix
A is defined as
where is a permutation over . Thus the permanent of
A is equal to the sum of the weights of all cycle-covers of the graph.
Perfect matchings
A square matrix can also be viewed as the biadjacency matrix of a
bipartite graphIn the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
which has
verticesIn graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
on one side and on the other side, with representing the weight of the edge from vertex to vertex . If the weight of a perfect matching that matches to is defined to be the product of the weights of the edges in the matching, then
Thus the permanent of
A is equal to the sum of the weights of all perfect matchings of the graph.
0-1 permanents: counting in unweighted graphs
In an unweighted, directed, simple graph, if we set each to be 1 if there is an edge from vertex
i to vertex
j, then each nonzero cycle cover has weight 1, and the adjacency matrix has 0-1 entries. Thus the permanent of a 01-matrix is equal to the
number of cycle-covers of an unweighted directed graph.
For an unweighted bipartite graph, if we set
ai,j = 1 if there is an
edgeIn mathematics and computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
between the vertices and and
ai,j = 0 otherwise, then each perfect matching has weight 1. Thus the number of perfect matchings in
G is equal to the permanent of matrix
A.
Computation of the permanent
The permanent is also more difficult to compute than the determinant. While the determinant can be computed in
polynomial timeIn computer science, polynomial time refers to the running time of an algorithm, that is, the number of computation steps a computer or an abstract machine requires to evaluate the algorithm....
by
Gaussian eliminationIn linear algebra, Gaussian elimination is an algorithm for solving systems of linear equations, finding the rank of a matrix, and calculating the inverse of an invertible square matrix. Gaussian elimination is named after German mathematician and scientist Carl Friedrich Gauss.Elementary row...
, Gaussian elimination cannot be used to compute the permanent. Moreover, computing the permanent of a 0-1 matrix (matrix whose entries are 0 or 1) is #P-complete. Thus, if the permanent can be computed in
polynomial timeIn computer science, polynomial time refers to the running time of an algorithm, that is, the number of computation steps a computer or an abstract machine requires to evaluate the algorithm....
by any method, then
FPIn computational complexity theory, the complexity class FP is the set of function problems which can be solved by a deterministic Turing machine in polynomial time; it is the function problem version of the decision problem class P...
= #PIn computational complexity theory, the complexity class #P is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute ƒ," where ƒ is the number of accepting paths of an NP machine...
which is an even stronger statement than
P = NPThe relationship between the complexity classes P and NP is an unsolved question in theoretical computer science and it is considered to be the most important problem in the field....
. When the entries of
A are nonnegative, however, the permanent can be computed
approximatelyIn computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
in
probabilisticA randomized algorithm or probabilistic algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all...
polynomial time, up to an error of ε
M, where
M is the value of the permanent and ε > 0 is arbitrary.
See also
- Bapat-Beg theorem
In probability theory, the Bapat–Beg theorem gives the joint cumulative distribution function of order statistics of independent but not necessarily identically distributed random variables in terms of the cumulative distribution functions of the random variables...
, an application of permanent in order statistics
- Permanent is #P-complete
In a 1979 paper Leslie Valiant proved that the problem of computing the permanent of a matrix is #P-hard, and remains #P-complete even if the matrix is restricted to have entries that are all 0 or 1. This result is known as Valiant's theorem and is considered a seminal result in computational...