Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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 ...
Deyi Chen's user avatar
  • 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 ...
Timothy Chow's user avatar
  • 82.7k
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$ ...
Deyi Chen's user avatar
  • 884
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 ...
S. Kohn's user avatar
  • 265
0 votes
0 answers
244 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 $...
joro's user avatar
  • 25.4k