As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [permanent]

The tag has no usage guidance.

77 questions
Filter by
Sorted by
Tagged with
1 vote
174 views

### Deciding if given number is a permanent of matrix

The permanent of an $n$-by- $n$ matrix $A=\left(a_{i j}\right)$ is defined as $$\operatorname{perm}(A)=\sum_{\sigma \in S_{n}} \prod_{i=1}^{n} a_{i, \sigma(i)}$$ The sum here extends over all ...
271 views

• 543
48 views

### Calculating permanents via Branch and Bound

Permanents can be interpreted as counting directed cycle covers of an asymmetric graph with unit cost edge weights. That interpretation leads to a branch and bound algorithm for calculating the ...
• 12k
1 vote
60 views

### On perfect matchings on planar graphs - is there a linear time deterministic algorithm?

The slides here provide a way to get a pfaffian orientation from Minimum Spanning Tree. MST can be found in linear time if graph is planar and weights are $1$ and the slides give a linear time ...
• 13.2k
226 views

### Spectral norm bound for lower triangular matrix

Let $A$ be a $0/1$ square matrix which can be permuted to a non singular or a singular lower triangular matrix. Determinant is either $0$ or $1$. Can we provide tighter upper bounds on its spectral ...
• 13.2k
255 views

### The calculation of permanent of a matrix

The permanent of an $n$-by- $n$ matrix $A=\left(a_{i j}\right)$ is defined as $$\operatorname{perm}(A)=\sum_{\sigma \in S_{n}} \prod_{i=1}^{n} a_{i, \sigma(i)}$$ The sum here extends over all ...
• 767
330 views

### Permanents and Kummer-like congruence

Recently, several of my conjectures in Question 402572 and Question 403336 were proved by Fu, Lin and Sun available from Proofs of five conjectures relating permanents to combinatorial sequences. ...
• 729
813 views

### Set partitions and permanents

Let $a(n)=$ Number of ordered set partitions of $[n]$ such that the smallest element of each block is odd. ...
• 729
57 views

### Sum of number of perfect matchings and a constant constuction

Suppose we have two bipartite graphs $G_1$ and $G_2$ with perfect matching count $P_1$ and $P_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P_1P_2$. Is ...
• 13.2k
475 views

### A novel identity connecting permanents to Bernoulli numbers

For a matrix $[a_{j,k}]_{1\le j,k\le n}$ over a field, its permanent is defined by $$\mathrm{per}[a_{j,k}]_{1\le j,k\le n}:=\sum_{\pi\in S_n}\prod_{j=1}^n a_{j,\pi(j)}.$$ In a recent preprint of mine, ...
• 13.7k
280 views

### Tangent numbers, secant numbers and permanent of matrices

Inspired by Question 402572, I consider the permanent of matrices $$f(n)=\mathrm{per}(A)=\mathrm{per}\left[\operatorname{sgn} \left(\sin\pi\frac{j+2k}{n+1} \right)\right]_{1\le j,k\le n},$$ where $n$ ...
• 729
625 views

The permanent $\mathrm{per}(A)$ of a matrix $A$ of size $n\times n$ is defined to be: $$\mathrm{per}(A)=\sum_{\tau\in S_n}\prod_{j=1}^na_{j,\tau(j)}.$$ Let $$A=\left[\tan\pi\frac{j+k}n\right]_{1\le j,... • 729 1 vote 0 answers 137 views ### The congruence \mathrm{per}[|j-k|]_{1\le j,k\le p}\equiv-1/2\pmod p with p an odd prime For a matrix [a_{j,k}]_{1\le j,k\le n}, its permanent is given by$$\mathrm{per}[a_{j,k}]_{1\le j,k\le n}=\sum_{\tau\in S_n}\prod_{j=1}^na_{j,\tau(j)}.$$Let p be an odd prime. I have proved the ... • 13.7k 21 votes 2 answers 1k views ### Euler numbers and permanent of matrices Motivated by Question 402249 of Zhi-Wei Sun, I consider the permanent of matrices$$e(n)=\mathrm{per}\left[\operatorname{sgn} \left(\tan\pi\frac{j+k}n \right)\right]_{1\le j,k\le n-1},$$where n is ... • 729 3 votes 1 answer 438 views ### On \frac{(-1)^{(n-1)/2}}n\mathrm{per}\left[\tan\pi\frac{j+k}n\right]_{1\le j,k\le n-1} with n\in\{3,5,7,\ldots\} Recall that the permanent of a matrix A=[a_{j,k}]_{1\le j,k\le n} is given by$$\mathrm{per}(A)=\sum_{\tau\in S_n}\prod_{j=1}^na_{j,\tau(j)}.$$Let n be an odd integer greater than one. In 2019 I ... • 13.7k 0 votes 1 answer 183 views ### \mathbb R and \mathbb F_2 rank in boolean matrix product By rank I imply rank over reals (\mathbb R). I consider two n\times n matrices A,B having entries in 0/1. The product below follows usual matrix product rules except xy is AND(x,y) and x+... • 23 4 votes 0 answers 182 views ### Dyadic distribution of 0/1 permanents Fix reals a,b\in(1,2) satisfying 1<b<a<ab<2. What fraction of 0/1 matrices of dimensions n\times n have permanents in [b2^m,a2^m] at some m\in\{0,1,2,\dots,\lfloor\log_2n!\... • 13.2k 4 votes 1 answer 141 views ### Subspaces of vanishing permanent Suppose that p\ge 5 is a prime, n a positive integer divisible by p-1, and L<\mathbb F_p^n a subspace of dimension d=n/(p-1). Do there exist vectors l_1,\dotsc,l_n\in L such that the ... • 22.2k 2 votes 2 answers 152 views ### growth of the permanent of some band matrix Consider such special band matrix of dimension n. It is a 0-1 matrix, and only the first few diagonals are nonzero. Specifically,$$ H_{ij} = 1 $$if and only if |i-j| \leq 2. How does the ... • 265 1 vote 0 answers 89 views ### Number of extremal \{0,1\} matrices having permanent 1 property Is there a function which describes the number of \{0,1\}^{n\times n}\cap\mathbb Z^{n\times n} matrices having permanent 1? I think it might be \mathsf{poly}(n!) bounded. Is there a function ... • 13.2k 3 votes 0 answers 71 views ### Bunch of matrices with vanishing permanents \DeclareMathOperator{\Per}{Per} \newcommand{\oI}{{\overline I}} \newcommand{\oJ}{{\overline J}} Is it possible to classify pairs (A,B) of square, nonsingular matrices over a field of prime ... • 22.2k 2 votes 0 answers 132 views ### Distinguishing 0/1 unimodular or singular matrices having \mathsf{Permanent}\in\{0,1\}? Let \mathcal T_n=\{M\in\{0,1\}^{n\times n}:\mathsf{Per}(M)=\mathsf{Det}(M)\wedge\mathsf{Det}(M)\in\{0,1\}\} (restricted set unimodular or singular having permanent and determinant identical). \... • 13.2k 2 votes 0 answers 105 views ### Standard interpretation of permanents (of orthogonal included) over finite fields Given a 0/1 matrix in \mathbb Z^{n\times n} the standard interpretation of permanent of the matrix is the number of perfect matchings in the underlying 2n vertex balanced bipartite graph with ... • 13.2k 7 votes 1 answer 182 views ### Reference for permanent integral identity \DeclareMathOperator\perm{perm}\DeclareMathOperator\diag{diag}Using MacMahon's master theorem, the properties of complex gaussian integrals, and Cauchy's integral theorem one can show that the ... • 241 5 votes 0 answers 69 views ### Permanent of matrices of finite order Assume M is a n \times n-matrix with entries in \mathbb{Z} such that M^k is the identity matrix for some k \geq 1. Question 1: Is the permanent of M non-zero? This is tested for many ... • 24.4k 22 votes 3 answers 1k views ### On permanents and determinants of finite groups \DeclareMathOperator\perm{perm}Let G be a finite group. Define the determinant \det(G) of G as the determinant of the character table of G over \mathbb{C} and define the permanent \perm(G)... • 24.4k 1 vote 1 answer 330 views ### Permanent of a matrix with duplicate rows/columns I'm trying to find an efficient algorithm/technique to calculate, or approximate, the permanent of a matrix. After reading some literature, it seems nothing exists faster than Ryser's algorithm in the ... • 113 6 votes 1 answer 239 views ### When is the log-permanent concave? Let \operatorname{PSD}_n be the cone of n\times n semidefinite positive matrices. For any X\in \operatorname{PSD}_n, define$$f(X)=\log(\det(X)).$$Then f is a concave function on \... • 3,650 -1 votes 1 answer 342 views ### On the permanent dominance conjecture for symmetric group The Lieb's permanent dominance conjecture states that the expression$$\frac{d_{\chi}^HA}{\chi(e)}\le per(A)$$holds for all positive semidefinite matrices A, where d_{\chi}^HA=\sum_\limits{\sigma\... • 1,823 19 votes 1 answer 2k views ### Is Van der Waerden's conjecture really due to Van der Waerden? Van der Waerden's conjecture (now a theorem of Egorychev and Falikman) states that the permanent of a doubly stochastic matrix is at least n!/n^n. The Wikipedia article, as well as many other ... • 72.9k 13 votes 1 answer 298 views ### Permanent of the Coxeter matrix of a distributive lattice Let L be a finite distributive lattice with n elements. Let C=(c_{x,y}) be the n \times n matrix with entry 1 in case x \leq y and 0 else. The Coxeter matrix of L is defined as the matrix ... • 24.4k 2 votes 0 answers 118 views ### Mod 2 of \#PM(G) for arbitrary G? Permanent mod 2 of biadjacency gives polynomial time algorithm of \#PM(G)\mod 2 of perfect matchings of bipartite graph. Is there a similar efficient strategy for general graphs? • 13.2k 1 vote 0 answers 64 views ### Planar graphs with perfect matching count in linear time? We can find Pfaffian orientation and take determinant to compute permanent in O(n^\omega) time where \omega is exponent of matrix multiplication. We know that permanent of O(n) vertex planar ... • 13.2k 1 vote 1 answer 83 views ### Maximum number of perfect matchings in a graph of genus g balanced k-partite graph What is the maximum number of perfect matchings a genus g balanced k-partite graph (number of vertices for each color in all possible k-colorings is within a difference of 1) can have? I am ... • 13.2k 2 votes 0 answers 77 views ### Statistics of perfect matching and incremental perfect matchings in bipartite planar graphs? Planar graph permanent can be reduced to determinants and so statistics should be amenable. Pick a uniformly random bipartite planar graph G with n vertices of each color and choose new additional ... • 13.2k 8 votes 1 answer 337 views ### Is the permanent of the matrix [(\frac{i+j}{2n+1})]_{0\le i,j\le n} always positive? Recall that the permanent of an n\times n matrix A=[a_{i,j}]_{1\le i,j\le n} is defined by$$\operatorname{per}A=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}.$$In 2004, R. Chapman [Acta ... • 13.7k 4 votes 0 answers 97 views ### Volume interpretation of number of perfect matchings in bipartite planar graphs Permanent of biadjacency of bipartite graphs is the number of perfect matchings. In the case of planar graphs we can obtain an orientation with sign changes and get away with computing the determinant ... • 13.2k 9 votes 1 answer 346 views ### On the permanent \text{per}[i^{j-1}]_{1\le i,j\le p-1} modulo p^2 Let p be an odd prime. It is well-known that$$\det[i^{j-1}]_{1\le i,j\le p-1}=\prod_{1\le i<j\le p-1}(j-i)\not\equiv0\pmod p.$$I'm curious about the behavior of the permanent \text{per}[i^{j-... • 13.7k 3 votes 2 answers 485 views ### On the sum \sum_{\pi\in S_{n}}e^{2\pi i\sum_{k=1}^{n}k\pi(k)/n} Motivated by Question 316142 of mine, I consider the new sum$$S(n):=\sum_{\pi\in S_{n}}e^{2\pi i\sum_{k=1}^{n}k\pi(k)/n}$$for any positive integer n, where S_n is the symmetric group of all the ... • 13.7k 7 votes 3 answers 615 views ### Distribution of sum of two permutation matrices Determinant and permanent of sum of two n\times n permutation matrices can be arbitrarily different. What is the distribution of determinant of sum and difference of two n\times n permutation ... • 13.2k 3 votes 0 answers 101 views ### Rank relation to maximum subpermanent and subdeterminant? Given a \pm1 matrix M of rank r let the largest subdeterminant be d and let the largest subpermanent be p. Are there relations/bounds that connect r, d and p? Are there geometric and ... • 13.2k 3 votes 1 answer 246 views ### Multi-dimensional permanent Is there a particularly natural / "correct" way of generalizing permanents to tensors? (I mean of course, 'square' tensors.) There seem to be very few resources on the matter. There needs to be a ... • 1,123 3 votes 1 answer 213 views ### On particular sumset properties of permanent? Denote \mathcal R_2[n]=\mathcal R[n] + \mathcal R[n] to be sumset of integers in \mathcal R[n] where \mathcal R[n] to be set of permanents possible with permanents of n\times n matrices with ... • 13.2k 2 votes 1 answer 366 views ### How hard is it to compute these prime factor related problems? We know that computing number of prime factors implies efficient factoring algorithm (How hard is it to compute the number of prime factors of a given integer?). Let \omega(n) be number of distinct ... • 13.2k 2 votes 0 answers 323 views ### Permanent of a matrix Let n \geq 2 a,b complex numbers (or in some other ring if you wish). What is the permanent of the matrix$$M(a,b,n)= \begin{bmatrix} a & a & a & ... & a & a \\ a &...
• 24.4k
In the course of discussing another MO question we realized that we did not know the answer to a more basic question, namely: Is it true that for every positive integer $k$ there exists a balanced ...