The permanent tag has no wiki summary.

**0**

votes

**0**answers

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

**20**

votes

**0**answers

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

**16**

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

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

**5**

votes

**4**answers

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

**11**

votes

**2**answers

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

**3**

votes

**2**answers

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