All Questions
Tagged with permanent linear-algebra
20 questions
1
vote
1
answer
205
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.8k
10
votes
1
answer
268
views
A bound for the permanent of a nonnegative matrix
Suppose $A=(a_{ij})$ is a symmetric (0,1)-matrix with 1's along the diagonal, and let $A_{ij}$ be the matrix obtained by removing the $i$-th row and $j$-th column.
Based on substantial numerical ...
- 105
2
votes
0
answers
354
views
Spectral norm bound for lower triangular matrix
Let $A$ be a $0/1$ square matrix which can be permuted to a non singular or a singular lower triangular matrix. Determinant is either $0$ or $1$. Can we provide tighter upper bounds on its spectral ...
- 13.9k
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
0
votes
1
answer
248
views
$\mathbb R$ and $\mathbb F_2$ rank in boolean matrix product
By rank I imply rank over reals ($\mathbb R$).
I consider two $n\times n$ matrices $A,B$ having entries in $0/1$.
The product below follows usual matrix product rules except $xy$ is $AND(x,y)$ and $x+...
- 23
4
votes
1
answer
173
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 ...
- 23k
3
votes
0
answers
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 ...
- 23k
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
votes
1
answer
383
views
On the permanent dominance conjecture for symmetric group
The Lieb's permanent dominance conjecture states that the expression $$\frac{d_{\chi}^HA}{\chi(e)}\le per(A)$$ holds for all positive semidefinite matrices $A$, where $d_{\chi}^HA=\sum_\limits{\sigma\...
- 2,089
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
2
votes
0
answers
123
views
Mod $2$ of $\#PM(G)$ for arbitrary G?
Permanent mod $2$ of biadjacency gives polynomial time algorithm of $\#PM(G)\mod 2$ of perfect matchings of bipartite graph. Is there a similar efficient strategy for general graphs?
- 13.9k
4
votes
0
answers
99
views
Volume interpretation of number of perfect matchings in bipartite planar graphs
Permanent of biadjacency of bipartite graphs is the number of perfect matchings. In the case of planar graphs we can obtain an orientation with sign changes and get away with computing the determinant ...
- 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
0
answers
364
views
Permanent of a matrix
Let $n \geq 2$ $a,b$ complex numbers (or in some other ring if you wish).
What is the permanent of the matrix
$$M(a,b,n)=
\begin{bmatrix}
a & a & a & ... & a & a \\
a &...
- 26.5k
2
votes
1
answer
118
views
What $n$-linear sums can be extracted from a product of linear polynomials in $m$ variables?
Let $\boldsymbol{c}_1, ..., \boldsymbol{c}_n$ be $n$ orthonormal, $m$-dimensional complex vectors, with $\boldsymbol{c}_i = (c_{i,1}, ..., c_{i,m})$.
Consider the following polynomial in $x_1,..., x_m$...
- 342
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
1
vote
0
answers
68
views
Zero as a repeated permanental root for a matrix over a finite field
All,
Suppose $A \in Mat(n, \mathbb{F}_{q})$ for $q$ prime, $q \geq 5$, and $n \geq 2^{q-2}$ . Let $\pi_A(x)$ be the permanental polynomial for $A$. That is,
\begin{equation*}
\pi_{A}(x)=per(xI-A).
\...
- 11
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
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
4
votes
2
answers
620
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)$ ...
- 6,962