Questions tagged [permanent]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
Timothy Chow's user avatar
  • 76.9k
28 votes
1 answer
772 views

Are there any nontrivial near-isometries of the $n$-dimensional cube?

Consider the $n$-dimensional Hamming cube, $C = \{-1,1\}^n$. Given an $n \times n$ orthogonal matrix $O$, I'll measure "how close $O$ is to being an isometry of $C$" by the following scoring function:...
Scott Aaronson's user avatar
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 ...
Turbo's user avatar
  • 13.5k
23 votes
1 answer
943 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
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.4k
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 ...
Deyi Chen's user avatar
  • 839
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
  • 76.9k
18 votes
3 answers
2k views

Silly me & Van der Waerden conjecture

So I walked into this very innocent-looking combinatorics problem, and quite soon I ended up with the problem to prove that any doubly stochastic $n \times n$ matrix has a non-zero permanent. Now ...
Per Alexandersson's user avatar
13 votes
2 answers
907 views

Computing a large permanent

Is there a practical way to compute the permanent of a large ($91 \times 91$) $(0,1)$ matrix? I have tried to use the matlab function written by Luke Winslow which works great for smaller matrices ...
Felix Goldberg's user avatar
13 votes
1 answer
306 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.4k
12 votes
3 answers
851 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
  • 839
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
9 votes
1 answer
650 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
  • 839
9 votes
1 answer
352 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.3k
8 votes
1 answer
350 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.3k
7 votes
1 answer
378 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$. ...
user43451's user avatar
  • 173
7 votes
3 answers
312 views

Concentration Bound of $0/1$ permanent

If I pick a random $0/1$ $n\times n$ matrix with $0$ occuring with probability $p$ then what does the distribution of the permanent look like?
Turbo's user avatar
  • 13.5k
7 votes
4 answers
611 views

Permanent identities for special classes of matrices

The permanent $P(M)$ of a matrix $M$ of size $n$ is defined to be: $$ P(M) := \sum_{\sigma \in S_n}\prod_{i=1}^n M_{i\sigma(i)} $$ If you have a matrix of the form $$ M_{ij} := A_i + B_j $$ where ...
Michael Burge's user avatar
7 votes
2 answers
276 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
7 votes
3 answers
649 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.5k
7 votes
1 answer
489 views

About an identity which gives immediate proof of the permanent lemma

Let $A$ be a $n \times n$ matrix over field $F$. Let $a_1, \cdots, a_n$ be the column vectors of $A$. For any subset $S \subseteq [n] = \{1, 2, \cdots, n\}$, let $a_S = \sum_{i \in S} a_i$. Alon's ...
Jineon Baek's user avatar
7 votes
1 answer
210 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
7 votes
0 answers
345 views

Missing count in number of perfect matchings

Let $f(G)$ give number of perfect matchings of a graph $G$. Denote $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$. Denote collection of all $2n$ vertex balanced bipartite graph to be $\mathcal G_{2n}$. ...
Turbo's user avatar
  • 13.5k
6 votes
2 answers
302 views

Permanent of Nakayama algebras

See https://en.wikipedia.org/wiki/Nakayama_algebra for the definition of Nakayama algebras and define the permanent of such an algebra to be the permanent of its Cartan matrix. (all algebras are ...
Mare's user avatar
  • 25.4k
6 votes
2 answers
290 views

On additive/multiplicative property of permanent

With $\Bbb K$ a commutative rings there a way to characterize $A,B\in\Bbb K^{n\times n}$ with $$Per(AB)=Per(A)Per(B)?$$ John provides a reasonable concept coverage multiplicative property. How about ...
user avatar
6 votes
2 answers
178 views

Permanent of a complete graph with negative cliques

Let $K_n$ be the complete graph on $n$ vertices. Inside $K_n$ there are $k$ negative(edge weight is equal to -1) complete subgraphs $K_{n_1}, K_{n_2},...,K_{n_k}$, which are vertex disjoint. Let $A(G)$...
Ranveer Singh's user avatar
6 votes
1 answer
323 views

Distribution of the permanent modulo $p$

We know that the order of $SL_n({\mathbb F}_p)$ is $$p^{n(n-1)/2}(p^n-1)(p^{n-1}-1)\cdots(p^2-1).$$ Dividing by $p^{n^2}$, we deduce the probability that $\det$ takes the value $1$ over $M_n({\mathbb ...
Denis Serre's user avatar
  • 50.6k
6 votes
1 answer
502 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.3k
6 votes
1 answer
250 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,740
5 votes
1 answer
338 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
  • 839
5 votes
1 answer
297 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.3k
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.4k
5 votes
0 answers
170 views

Permanent bound for Laplacian matrix of signed graph

In 1986, Prof. RB Bapat shown that (see here) if $G$ is a simple connected graph on $n$ vertices, then, the permanent per$\big(L(G)\big)\ge 2(n-1)\kappa(G)$, where $L(G)$ is the Laplacian matrix of $G$...
Ranveer Singh's user avatar
4 votes
2 answers
607 views

Is Ryser's conjecture on permanent minimizers still open?

Let $A(k,n)$ be the set of $\{0,1\}$ matrices of order $n$ with all their line sums equal to $k$. Conjecture number 5 on the list from Minc's book, attributed to Ryser, says that if $A(k,n)$ ...
Felix Goldberg's user avatar
4 votes
1 answer
152 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.6k
4 votes
0 answers
186 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.5k
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.5k
3 votes
2 answers
511 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.3k
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.3k
3 votes
1 answer
295 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
  • 839
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.5k
3 votes
1 answer
275 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,183
3 votes
1 answer
163 views

Permanent of distorted matrix

Let $J$ be all $1$ matrix. Suppose permanent of $M$ is $p$ and $a\in\Bbb Z$. Is there a closed formula or at least a faster than Ryser's technique to find $Permanent(M+aJ)$?
Turbo's user avatar
  • 13.5k
3 votes
0 answers
208 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,769
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.6k
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.5k
3 votes
0 answers
366 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 ...
user avatar
3 votes
0 answers
228 views

Multi-dimensional permanent of structured tensor

I am facing the multidimensional permanent \begin{equation} \text{perm}(W) = \sum_{\sigma, \rho \in S_n} \prod_{j=1}^n W_{j, \sigma_j, \rho_j } \end{equation} of a 3-tensor $W_{j,k,l}$ of ...
Malte's user avatar
  • 93
2 votes
2 answers
158 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
2 votes
1 answer
385 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 ...
Turbo's user avatar
  • 13.5k