All Questions
Tagged with permanent linear-algebra
9 questions with no upvoted or accepted answers
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
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
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
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
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
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
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
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
-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