Questions tagged [permanent]
The permanent tag has no usage guidance.
83 questions
2
votes
0
answers
214
views
A conjectured generalization of Marcus's inequality
Note: I have edited the post below in order to include sharper (conjectured) inequalities, using $|H_1 \cap H_2|$.
Let $[n] = \{1, \dots, n\}$ and let $\sim$ be an equivalence relation on $[n]$. Then $...
- 5,215
1
vote
0
answers
119
views
Why can permanents and hafnians be viewed as partition functions?
In the description of the book "Combinatorics and Complexity of Partition Functions", by Alexander Barvinok, it is written "...The main focus of the book is on efficient ways to compute ...
- 5,215
0
votes
0
answers
13
views
Enumerating the directed vertex-disjoint cycle covers of digraphs
A directed cycle-cover of a digraph $D$ is in the sense of this post equivalent to a perfect matching in the related undirected biadjacency graph $B$ in which the edges connect a vertex $u$ of $D$ in ...
- 13.2k
1
vote
1
answer
205
views
Van der Waerden conjecture and Alexandrov-Fenchel inequality
The Van der Waerden conjecture is a lower estimate of the permanent of a doubly stochastic matrix. In this article in Wikipedia it is stated that Egorychev's proof uses the Alexandrov-Fenchel ...
- 21.8k
3
votes
2
answers
327
views
An analogue of Jacobi's formula for the matrix permanent
Is there an analogoue to Jacobi's formula for the matrix permanent?
- 52.4k
3
votes
0
answers
219
views
Do these cousins of permanents satisfy the following inequality?
Let $H$ denote an $n$ by $n$ hermitian positive semidefinite matrix. Let $G$ and $K$ be two subgroups of the symmetric group $\Sigma_n$. Define
$$ f_{G, K}(H) = \sum_{(\sigma, \tau) \in G \times K} \...
- 5,215
28
votes
3
answers
2k
views
Is every positive integer the permanent of some 0-1 matrix?
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 ...
- 82.7k
-1
votes
1
answer
446
views
What is wrong with the argument that zero permanent is polynomial?
This Lecture summarizes some well known facts about $\#P$ completeness of permanent.
Given a CNF formula $\phi$ on $n$ variables, they construct
matrix $A$ such that:
$$perm(A)=4^{3m} \#SAT(\phi)$$
...
CommunityBot
- 1
5
votes
1
answer
319
views
A conjectural permanent identity
Let $n>1$ be an integer, and let $\zeta$ be a primitive $n$th root of unity. By $(3.4)$ of arXiv:2206.02589, $1$ and those $n+1-2s\ (s=1,\ldots,n-1)$ are all the eigenvalues of the matrix $M=[m_{jk}...
- 15.6k
1
vote
1
answer
209
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 ...
- 47.6k
1
vote
0
answers
176
views
Some $p$-adic congruences involving permutations
Motivated by my study of determinants and permanents, here I present several conjectures on $p$-adic congruences involving permutations.
As usual, we let $S_n$ be the symmetric group consisting of all ...
- 15.6k
10
votes
1
answer
268
views
A bound for the permanent of a nonnegative matrix
Suppose $A=(a_{ij})$ is a symmetric (0,1)-matrix with 1's along the diagonal, and let $A_{ij}$ be the matrix obtained by removing the $i$-th row and $j$-th column.
Based on substantial numerical ...
- 105
6
votes
1
answer
520
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, ...
CommunityBot
- 1
3
votes
0
answers
372
views
On the precise concentration of permanent of $\pm1$ matrices
Obtain $M\in\{-1,+1\}^{n\times n}$ by unbiased coin flipping.
What is known about the distribution of permanent $\mathsf{Perm}(M)$? It seems to be bimodal.
Given a function $g(n)$ what is the ...
CommunityBot
- 1
7
votes
2
answers
366
views
On permanent of a square of a doubly stochastic matrix
Let $A = (a_{i,j})$ be a double stochastic matrix with positive entries. That is, all entries are positive real numbers, and each row and column sums to one. A permanent of a matrix $A = (a_{i,j})$ is ...
- 341
23
votes
1
answer
1k
views
Symmetric polynomial inequality arising from the fixed-point measure of a random permutation
A somewhat strange elementary polynomial inequality came up recently in my work, and I wonder if anyone has seen other things that are reminiscent of what follows.
Given $n$ non-negative reals $a_1, ...
CommunityBot
- 1
4
votes
1
answer
173
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 ...
- 149k
2
votes
0
answers
50
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 ...
- 13.2k
1
vote
0
answers
69
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.9k
2
votes
0
answers
354
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.9k
7
votes
1
answer
256
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
2
votes
0
answers
489
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 ...
- 63.9k
12
votes
3
answers
892
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.
...
- 884
5
votes
1
answer
346
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.
...
- 884
20
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 ...
- 101
3
votes
1
answer
308
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$ ...
- 15.6k
2
votes
0
answers
60
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.9k
25
votes
3
answers
2k
views
Interpretations and models of permanent
The standard interpretation of permanent of a $0/1$ matrix if considered as a biadjacency matrix of a bipartite graph is number of perfect matchings of the graph or if considered as a adjacency matrix ...
- 13.9k
9
votes
1
answer
676
views
Permanent identities
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,...
- 15.6k
1
vote
0
answers
138
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 ...
- 15.6k
3
votes
1
answer
457
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 ...
- 884
8
votes
1
answer
364
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 ...
- 690
0
votes
1
answer
248
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+...
- 15.4k
4
votes
0
answers
99
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.9k
4
votes
0
answers
187
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.9k
2
votes
2
answers
193
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 ...
- 17k
1
vote
0
answers
94
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.9k
3
votes
0
answers
75
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 ...
- 23k
2
votes
0
answers
137
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.9k
9
votes
1
answer
357
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-...
- 34.3k
2
votes
0
answers
111
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.9k
7
votes
1
answer
297
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 $\...
- 52.4k
5
votes
0
answers
76
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 ...
- 26.5k
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)...
- 33.8k
13
votes
1
answer
311
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 $...
- 33.8k
1
vote
1
answer
698
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 ...
- 2,720
-1
votes
1
answer
383
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\...
CommunityBot
- 1
20
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 ...
- 82.7k
7
votes
1
answer
383
views
A generalization of van der Waerden's conjecture
I am wondering if the following generalization of van der Waerden's conjecture is true.
Suppose A is an n x n non-negative matrix with all column sums equal to 1, and the sum of row i equal to $T_i$. ...
- 2,493
2
votes
0
answers
123
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?
- 63.9k