Questions tagged [permanent]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
165 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 ...
asv's user avatar
  • 21.1k
3 votes
2 answers
272 views

An analogue of Jacobi's formula for the matrix permanent

Is there an analogoue to Jacobi's formula for the matrix permanent?
Sela Fried's user avatar
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} \...
Malkoun's user avatar
  • 4,981
1 vote
1 answer
201 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 ...
Alexandr Dorofeev's user avatar
5 votes
1 answer
301 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}...
Zhi-Wei Sun's user avatar
  • 14.4k
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 ...
Zhi-Wei Sun's user avatar
  • 14.4k
10 votes
1 answer
255 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 ...
ngm's user avatar
  • 105
7 votes
2 answers
298 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 ...
user avatar
23 votes
1 answer
965 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, ...
BPN's user avatar
  • 543
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 ...
Manfred Weis's user avatar
  • 12.6k
1 vote
0 answers
65 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 ...
Turbo's user avatar
  • 13.7k
2 votes
0 answers
309 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 ...
Turbo's user avatar
  • 13.7k
2 votes
0 answers
426 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 ...
Jacob.Z.Lee's user avatar
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. ...
Deyi Chen's user avatar
  • 844
12 votes
3 answers
864 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. ...
Deyi Chen's user avatar
  • 844
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 ...
Turbo's user avatar
  • 13.7k
6 votes
1 answer
506 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, ...
Zhi-Wei Sun's user avatar
  • 14.4k
3 votes
1 answer
297 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$ ...
Deyi Chen's user avatar
  • 844
9 votes
1 answer
655 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,...
Deyi Chen's user avatar
  • 844
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 ...
Zhi-Wei Sun's user avatar
  • 14.4k
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 ...
Deyi Chen's user avatar
  • 844
3 votes
1 answer
450 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 ...
Zhi-Wei Sun's user avatar
  • 14.4k
0 votes
1 answer
229 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+...
User2021's user avatar
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!\...
Turbo's user avatar
  • 13.7k
4 votes
1 answer
160 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 ...
Seva's user avatar
  • 22.8k
2 votes
2 answers
176 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 ...
S. Kohn's user avatar
  • 265
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 ...
Turbo's user avatar
  • 13.7k
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 ...
Seva's user avatar
  • 22.8k
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). $\...
Turbo's user avatar
  • 13.7k
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 ...
Turbo's user avatar
  • 13.7k
7 votes
1 answer
233 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 ...
motherboard's user avatar
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 ...
Mare's user avatar
  • 25.8k
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)...
Mare's user avatar
  • 25.8k
1 vote
1 answer
534 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 ...
chasmani's user avatar
  • 113
6 votes
1 answer
266 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 $\...
Bill Bradley's user avatar
  • 3,809
-1 votes
1 answer
369 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\...
vidyarthi's user avatar
  • 2,007
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 ...
Timothy Chow's user avatar
  • 78.1k
13 votes
1 answer
308 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 $...
Mare's user avatar
  • 25.8k
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?
Turbo's user avatar
  • 13.7k
1 vote
0 answers
74 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 ...
Turbo's user avatar
  • 13.7k
1 vote
1 answer
89 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 ...
Turbo's user avatar
  • 13.7k
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 ...
Turbo's user avatar
  • 13.7k
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 ...
Zhi-Wei Sun's user avatar
  • 14.4k
4 votes
0 answers
98 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 ...
Turbo's user avatar
  • 13.7k
9 votes
1 answer
353 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-...
Zhi-Wei Sun's user avatar
  • 14.4k
3 votes
2 answers
518 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 ...
Zhi-Wei Sun's user avatar
  • 14.4k
7 votes
3 answers
665 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 ...
Turbo's user avatar
  • 13.7k
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 ...
Turbo's user avatar
  • 13.7k
3 votes
1 answer
287 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 ...
Alex Meiburg's user avatar
  • 1,193
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 $...
Turbo's user avatar
  • 13.7k