Permanent (mathematics)

Permanent

Field	Linear algebra
Subfield
Notation
Named after
Invented by
Definitions
Theorems
Conjectures
Major publications
Related topics

The permanent is a mathematical concept that is closely related to the determinant. In the field of linear algebra, the permanent of a square matrix is a function that operates on the matrix and returns a scalar value. It is denoted by the symbol "perm" or "Per" and is defined as the sum of all possible products of the entries of the matrix, where each product consists of one entry from each row and one entry from each column.

Definition

Given an n × n matrix A, the permanent of A is defined as:

perm(A) = ∑_σ∈Sn a_1,σ(1) a_2,σ(2) ... a_n,σ(n),

where S_n is the set of all permutations of the numbers 1 through n, and a_i,j represents the entry in the i-th row and j-th column of the matrix A. In other words, the permanent is the sum of the products of the matrix entries, where each product is formed by taking one entry from each row and one entry from each column, and the entries are taken in the order specified by a permutation.

Properties

The permanent shares some similarities with the determinant, but there are also key differences between the two. One notable difference is that the permanent is not an alternating function like the determinant. This means that permuting two rows or two columns of a matrix does not change its permanent, whereas it does change the sign of the determinant.

Another important property of the permanent is that it is not easily computable. In fact, computing the permanent of a matrix is known to be a #P-complete problem, which means that it is computationally difficult. There is no known efficient algorithm for computing the permanent of a general matrix, unlike the determinant which can be computed in polynomial time.

Applications

The permanent has various applications in different areas of mathematics and computer science. One notable application is in the study of graph theory. The permanent of the adjacency matrix of a graph can be used to count the number of perfect matchings in the graph. A perfect matching is a set of edges in a graph such that every vertex is incident to exactly one edge in the set. The permanent provides a way to count the number of such matchings, which has important implications in combinatorial optimization and network analysis.

The permanent also appears in the study of quantum mechanics, particularly in the context of quantum computing. It is used in the analysis of quantum circuits and quantum algorithms, where it plays a role in determining the probability amplitudes of certain quantum states.

See also

• Determinant
• Matrix (mathematics)
• Graph theory
• Quantum computing