All Questions
17 questions
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
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
7
votes
1
answer
297
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 $\...
- 3,979
5
votes
0
answers
76
views
Permanent of matrices of finite order
Assume $M$ is a $n \times n$-matrix with entries in $\mathbb{Z}$ such that $M^k$ is the identity matrix for some $k \geq 1$.
Question 1: Is the permanent of $M$ non-zero?
This is tested for many ...
- 26.5k
3
votes
2
answers
327
views
An analogue of Jacobi's formula for the matrix permanent
Is there an analogoue to Jacobi's formula for the matrix permanent?
- 135
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
3
votes
1
answer
220
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 $...
- 13.9k
3
votes
1
answer
170
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)$?
- 13.9k
3
votes
0
answers
104
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.9k
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
561
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 &...
- 4,484
2
votes
0
answers
179
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} && \...
- 181
1
vote
1
answer
698
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
1
vote
1
answer
209
views
Deciding if given number is a permanent of matrix
The permanent of an $n$-by- $n$ matrix $A=\left(a_{i j}\right)$ is defined as
$$
\operatorname{perm}(A)=\sum_{\sigma \in S_{n}} \prod_{i=1}^{n} a_{i, \sigma(i)}
$$
The sum here extends over all ...
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
-1
votes
1
answer
446
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)$$
...
- 25.4k