Questions tagged [determinant]
The determinant tag has no usage guidance.
27
questions
1
vote
1
answer
55
views
Coefficients of a determinant of a matrix of univariate polynomials is in $GapL$
Given any matrix of univariate polynomials of degree $\leq n^{O(1)}$ then prove that the coefficent of $x^i$ in the determinant of the matrix is in $GapL$
Hint: Use Mahajan-Vinay's result of ...
- 288
0
votes
0
answers
56
views
Is there a construction which multiplies and adds spanning trees in Logspace?
I.1 Suppose we have two planar graphs $G_1$ and $G_2$ with spanning tree count $C_1$ and $C_2$ respectively then is there a graph construction in Logspace to get a planar graph from $G_1$ and $G_2$ ...
- 12.8k
3
votes
0
answers
137
views
On perm+1 and det+1
Given a balanced bipartite graph G and a planar graph H. We do not know the number of perfect matchings in G and we do not know the number of spanning trees in H. But assume they are at least 3 both.
...
- 12.8k
5
votes
1
answer
143
views
Can a sum of polynomially many determinants be expressed as a single determinant of a poly-size matrix?
(copied from a mathoverflow question because I realized this may be more appropriate for it) Let $A_1,A_2,...,A_k$ be $N$-by-$N$ matrices, with indeterminate entries in some field (say real or complex ...
- 225
27
votes
1
answer
439
views
How many multiplications are needed to compute the determinant of a 3×3 matrix?
In a comment on this question in 2016, Jeffrey Shallit remarked:
I've asked experts about this, and apparently it is not even currently known whether or not 9 multiplications are needed to compute ...
- 761
8
votes
0
answers
189
views
"Addition function" that works for both perm and det simultaneously?
For $f = (f_n)$ a family of polynomials where $f_n$ is a polynomial in $n^2$ variables (which we can think of as the entries of an $n \times n$ matrix), say a function $S(A,B)$ is an addition function ...
- 36.9k
0
votes
0
answers
80
views
On Determinant modulo $2^k$ complexity
Determinant of integer matrix modulo $2$ is complete for the class $\oplus L$. Is determinant modulo $2^k$ computable in $\oplus L$ at any fixed $k$?
How about if $k=o(n)$ where matrix is $n\times n$?
- 12.8k
2
votes
0
answers
149
views
Is the following problem in $coNP$?
Given an $n\times n$ matrix $M$ with $\mathbb Z$ entries is 'does an $\frac n2\times\frac n2$ minor of $M$ vanish?' in $\bf{coNP}$?
At least one $\frac n2\times\frac n2$ minor non-vanish implies rank ...
- 12.8k
2
votes
1
answer
156
views
Application of weak determinantal identities to GCT?
In general determinants have many identities. Would it help the $GCT$ program by invoking the paradigm of identities such as to state that if the permanent is converted to determinant then it has to ...
- 12.8k
2
votes
1
answer
209
views
Complexity of $\{0,\pm1\}$ determinant in sparse cases?
If $M\in\{-1,0,+1\}^{n\times n}$ be a matrix with only $O(n)$ non-zero entries and hadamard product $M\odot M$ being symmetric can we compute $Det(M)$ in $O(n)$ bit complexity?
Assume that the matrix ...
- 12.8k
6
votes
1
answer
369
views
Maximum Polyhedron Volume in Given $n$ Points
Suppose we are given $n$ points $v_1,v_2,\cdots, v_n\in \mathbb{R}^k$, I want to find $k+1$ points $v_{i_1}, v_{i_2},\cdots,v_{i_{k+1}}$ such that the volume of the convex body spanned by them ...
- 271
2
votes
1
answer
199
views
Complexity of computing generalised determinants. (P - #P transition)
Computing the determinant of a matrix can be done in polynomial time, while computing the permanent is known to be #P-hard. Let $A$ be an $n \times n$ matrix. Define a generalised determinant function ...
- 141
15
votes
1
answer
3k
views
The minimum number of arithmetic operations to compute the determinant
Has there been any work on finding the minimum number of elementary arithmetic operations needed to compute the determinant of an $n$ by $n$ matrix for small and fixed $n$? For example, $n=5$.
- 3,950
1
vote
0
answers
27
views
A question about a claim in "No occurrence obstructions in geometric complexity theory"
It the new preprint
Peter Bürgisser, Christian Ikenmeyer, Greta Panova, "No occurrence obstructions in geometric complexity theory", 2016
it is stated that
1.3. Conjecture (Mulmuley and Sohoni ...
- 12.8k
5
votes
1
answer
197
views
Implications of a recent negative result to geometric complexity
A paper was posted in arxiv http://arxiv.org/pdf/1512.03798.pdf titled 'Rectangular Kronecker coefficients and plethysms in geometric
complexity theory' by Christian Ikenmeyer and Greta Panova with ...
- 12.8k
5
votes
0
answers
250
views
What is the status of Determinantal Complexity of Permanent
Recently Landsberg and Ressayre announced an exponential lower bound for permanent's determinantal complexity assuming certain symmetry conditions.
What is the status of the problem of Permanent's ...
user34945
2
votes
0
answers
127
views
Complexity of a particular determinant
Suppose we have an $n\times n$ matrix $A$ with non-negative integer entries such that $\mathsf{Tr}(A^i)=0$ at every $i\in\{1,2,\dots,n-2,n-1\}$ and $\mathsf{Tr}(A^n)\neq0$, then from Trace-Determinant ...
user34945
12
votes
1
answer
815
views
Expressing Determinant as Permanent
One major problem in TCS is the problem of expressing a permanent as a determinant. I was reading Agrawal's paper Determinant Versus Permanent and in one paragraph he claims the reverse problem is ...
- 131
4
votes
1
answer
447
views
state-of-the-art bit complexity of the determinant
I'm trying to understand the full bit-complexity of computing the determinant of an $n\times n$ integer matrix, with each entry represented by $M$ bits.
I would like to know what is the state-of-the-...
- 1,224
11
votes
2
answers
1k
views
Determinants and Matrix Multiplication - Similarity and differences in algorithmic complexity and arithmetic circuit size
I am trying to understand the relation between algorithmic complexity and circuit complexity of Determinants and Matrix Multiplication.
It is known that the determinant of an $n\times n$ matrix can ...
- 12.8k
10
votes
2
answers
803
views
Cancellation and determinant
Berkowitz algorithm provides a polynomial size circuit with logarithmic depth for determinant of a square matrix using matrix powers. The algorithm implicitly uses cancellation. Is cancellation ...
- 12.8k
16
votes
1
answer
533
views
Implications of approximating the determinant
It is known that one can compute exactly the determinant of an $n\times n$ matrix in determinstic $\log^2(n)$ space.
What would be the complexity implications of approximating the determinant of a ...
- 1,224
8
votes
0
answers
305
views
Grigoriev-Karpinski for the permanent
Grigoriev and Karpinski (ps.Z) showed that any depth-3 circuit over a fixed finite field computing $\mathrm{Det}_n$ requires $2^{\Omega(n)}$ size. I had the misconception(?) until recently that the ...
- 2,482
8
votes
0
answers
195
views
Counting small terms in a determinant calculation over polynomials (counting spanning trees by weight)
I have a $n\times n$ matrix $A$. It's terms are $a_{ij}=-x^{w_{ij}}$ if $i\neq j$ and $a_{ii}=\sum_{j=0}^{n+1} x^{w_{ij}}$ on the diagonal. The matrix is symmetric as $w_{ij}=w_{ji}$. Numbers $w_{ij}$ ...
- 101
22
votes
2
answers
2k
views
Lower bound for determinant and permanent
In light of the recent chasm at depth-3 result (which among other things yields a $2^{\sqrt{n}\log{n}}$ depth-3 arithmetic circuit for the $n \times n $ determinant over $\mathbb{C}$), I have the ...
- 1,344
13
votes
1
answer
929
views
Smallest known formula for the determinant
The smallest known formula for the determinant has size $n^{\mathcal O(\log n)}$ according to the folklore (or to Ran Raz in its paper Multi-Linear Formulas for Permanent and Determinant are of Super-...
- 4,439
14
votes
2
answers
1k
views
Gaussian Elimination in terms of Group Action
Gaussian elimination makes determinant of a matrix polynomial-time computable. The reduction of complexity in computing the determinant, which is otherwise sum of exponential terms, is due to ...
- 1,281