Questions tagged [permanent]
The permanent tag has no usage guidance.
16 questions
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 ...
- 884
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 ...
- 82.7k
20
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 ...
- 82.7k
6
votes
2
answers
309
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 ...
- 26.5k
3
votes
1
answer
457
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 ...
- 15.6k
3
votes
1
answer
308
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$ ...
- 884
13
votes
2
answers
946
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 ...
- 6,962
13
votes
1
answer
311
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 $...
- 26.5k
12
votes
3
answers
892
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.
...
- 884
7
votes
0
answers
349
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}$.
...
- 13.9k
6
votes
1
answer
520
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, ...
- 15.6k
3
votes
0
answers
219
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} \...
- 5,215
3
votes
0
answers
237
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 ...
- 93
2
votes
2
answers
193
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
2
votes
1
answer
139
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 ...
- 3,041
0
votes
0
answers
245
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 $...
- 25.4k