# Questions tagged [permanent]

The permanent tag has no usage guidance.

**6**

votes

**0**answers

207 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

33 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

182 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

280 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

307 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

46 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

114 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

197 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

228 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

190 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

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

**22**

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

100 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

54 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

96 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

127 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

243 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

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

**5**

votes

**2**answers

220 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

270 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

160 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

280 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

286 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

109 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

176 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

63 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

265 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

123 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

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

**6**

votes

**1**answer

359 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

177 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

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

**15**

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

**6**

votes

**1**answer

267 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

436 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

778 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

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