3
votes
Coefficients of a determinant of a matrix of univariate polynomials is in $GapL$
Theorem 3.2 in this paper: https://doi.org/10.1007/s00224-003-1077-7 says this:
Let B be an n × n matrix, whose entries are each polynomials of degree n in
Z[x], where the coefficients of each ...
- 1,761
3
votes
Johnson-Lindenstrauss and the largest eigenvalue of a matrix
The answer to this question is no - thanks to Pravesh Kothari for the solution below and appreciate ideas from Clement Canonne and Christopher Chubb.
Consider two cases: 1) A is rank one, in which ...
- 253
3
votes
Johnson-Lindenstrauss and the largest eigenvalue of a matrix
I had thought I used something like this in a previous paper, but on checking I only needed the vector-based version. I'm not quite sure how to get the upper bound, but I think you can get the lower ...
2
votes
Complexity of Finding the Eigendecomposition of a Matrix
Here is a relatively recent answer that answers this (mostly) in the affirmative:
Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time
Where the ...
- 121
1
vote
Condition Number dependent algorithms for matrix operations
This was meant as a comment, but too long.
If we fix matrix norm to be 1, we can ask - which algorithms terminate faster when smallest eigenvalue is far from zero?
We can rule out algebraic algorithms ...
- 4,681
Only top scored, non community-wiki answers of a minimum length are eligible