# Questions tagged [permanent]

The permanent tag has no usage guidance.

80
questions

1
vote

1
answer

174
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 ...

3
votes

2
answers

285
views

### An analogue of Jacobi's formula for the matrix permanent

Is there an analogoue to Jacobi's formula for the matrix permanent?

3
votes

0
answers

209
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} \...

1
vote

1
answer

204
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 ...

5
votes

1
answer

304
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}...

1
vote

0
answers

173
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 ...

10
votes

1
answer

258
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 ...

7
votes

2
answers

329
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 ...

23
votes

1
answer

975
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, ...

2
votes

0
answers

49
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 ...

1
vote

0
answers

66
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 ...

2
votes

0
answers

313
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 ...

2
votes

0
answers

450
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 ...

5
votes

1
answer

339
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.
...

12
votes

3
answers

868
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.
...

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 ...

6
votes

1
answer

509
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, ...

3
votes

1
answer

301
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$ ...

9
votes

1
answer

657
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,...

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 ...

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 ...

3
votes

1
answer

451
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 ...

0
votes

1
answer

233
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+...

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!\...

4
votes

1
answer

162
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 ...

2
votes

2
answers

177
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 ...

1
vote

0
answers

92
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 ...

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 ...

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).
$\...

2
votes

0
answers

108
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 ...

7
votes

1
answer

236
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 ...

5
votes

0
answers

73
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 ...

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)...

1
vote

1
answer

588
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 ...

6
votes

1
answer

276
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 $\...

-1
votes

1
answer

370
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\...

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 ...

13
votes

1
answer

310
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 $...

2
votes

0
answers

121
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?

1
vote

0
answers

75
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 ...

1
vote

1
answer

90
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 ...

2
votes

0
answers

83
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 ...

8
votes

1
answer

353
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 ...

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 ...

9
votes

1
answer

354
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-...

3
votes

2
answers

521
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 ...

7
votes

3
answers

671
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 ...

3
votes

0
answers

103
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 ...

3
votes

1
answer

293
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 ...

3
votes

1
answer

218
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 $...