# Questions tagged [permanent]

The tag has no usage guidance.

80 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
• 21.2k
285 views

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

Is there an analogoue to Jacobi's formula for the matrix permanent?
• 135
209 views

• 844
1 vote
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 ...
• 14.6k
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 ...
• 844
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 ...
• 14.6k
233 views

• 13.7k
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 ...
• 22.8k
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 ...
• 265
1 vote
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 ...
• 13.7k
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 ...
• 22.8k
137 views

• 26.2k
1 vote
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 ...
• 113
276 views

• 2,079
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 ...
• 79.3k
310 views

• 14.6k
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 ...
• 14.6k
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 ...
• 13.7k
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 ...
• 13.7k
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 ...
• 1,203
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 \$...