# Questions tagged [permanent]

The permanent tag has no usage guidance.

46
questions

**5**

votes

**1**answer

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

**0**

votes

**1**answer

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

**18**

votes

**1**answer

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

**12**

votes

**1**answer

210 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

106 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

50 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

63 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

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

**6**

votes

**0**answers

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

**2**

votes

**0**answers

43 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

**0**answers

246 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

332 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

391 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

59 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

150 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

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

**2**

votes

**1**answer

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

**2**

votes

**0**answers

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

**23**

votes

**3**answers

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

**6**

votes

**2**answers

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

**23**

votes

**2**answers

1k views

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

**2**

votes

**1**answer

102 views

### An inequality between permanents of non-negative matrices

Let $A$ be a non-negative (all entries $\geq 0$) square matrix. Is it always true that
$$
(a_{11}+a_{12}+a_{21}+a_{22})^2\geq 4a_0a_2
$$
where
$a_{ij}$ is the permanent of a matrix obtained by ...

**2**

votes

**0**answers

57 views

### Minimum size of genus $g$ bipartite graphs with $2^n$ perfect matchings

Given $n\in\Bbb Z_{\geq0}$ let $2T_{n,g}$ be size of smallest number of vertices of genus $g$ bipartite graph with $T_{n,g}$ vertices of each color such that number of perfect matchings is $2^n$.
Eg: ...

**2**

votes

**1**answer

103 views

### What $n$-linear sums can be extracted from a product of linear polynomials in $m$ variables?

Let $\boldsymbol{c}_1, ..., \boldsymbol{c}_n$ be $n$ orthonormal, $m$-dimensional complex vectors, with $\boldsymbol{c}_i = (c_{i,1}, ..., c_{i,m})$.
Consider the following polynomial in $x_1,..., x_m$...

**5**

votes

**0**answers

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

**7**

votes

**3**answers

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

**3**

votes

**1**answer

134 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)$?

**6**

votes

**2**answers

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

**3**

votes

**0**answers

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

**6**

votes

**2**answers

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

**7**

votes

**0**answers

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

**2**

votes

**1**answer

343 views

### Vanishing of permanent of a Vandermonde matrix [Edited]

Does there exist an explicit criterion (or a good sufficient condition) for proving that a Vandemonde matrix:
$$A(x_1,\dots,x_n):=\left[ \begin{array}{llll}1 & x_1 &\dots& x_1^{n-1}\\ 1 &...

**1**

vote

**0**answers

119 views

### FPTAS for approximating the permanent of a matrix

My question concerns approximating permanent of an $n$-by-$n$ matrix.
Several approximation algorithms have been proposed in the literature for this purpose, whose time complexity depend on $n$ and ...

**0**

votes

**0**answers

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

**1**

vote

**0**answers

64 views

### Zero as a repeated permanental root for a matrix over a finite field

All,
Suppose $A \in Mat(n, \mathbb{F}_{q})$ for $q$ prime, $q \geq 5$, and $n \geq 2^{q-2}$ . Let $\pi_A(x)$ be the permanental polynomial for $A$. That is,
\begin{equation*}
\pi_{A}(x)=per(xI-A).
\...

**6**

votes

**1**answer

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

**2**

votes

**0**answers

158 views

### Does this permanent have a closed form?

What is the closed form of this permanent? (similar to the Cauchy determinant)
\begin{aligned}
f(z_1,z_2,\cdots,z_N,w_1,w_2,\cdots,w_N)=\left[
\small{\begin{matrix}
\frac{1}{(z_1-w_1)^2} && \...

**3**

votes

**0**answers

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

**7**

votes

**1**answer

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

**0**

votes

**0**answers

187 views

### Reduction from permanent to $(0,1)$-permanent and implication of $P \ne NP$

Valiant
shows reduction from counting the solutions of CNF formula $F$,$\#SAT(F)$
to computing permanent where $ Perm(A)= 4^{t(F)}\cdot \#SAT(F)$
for certain efficiently computable $t(F)$ and matrix $...

**28**

votes

**1**answer

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

**16**

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

**7**

votes

**1**answer

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

**7**

votes

**4**answers

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

**13**

votes

**2**answers

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

**4**

votes

**2**answers

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