Questions tagged [linear-algebra]
Linear algebra deals with vector spaces and linear transformations.
227
questions
19
votes
4
answers
992
views
Checking if all products of a set of matrices eventually equal zero
I am interested in the following problem: given integer matrices $A_1,A_2, \ldots, A_k$ decide if every infinite product of these matrices eventually equals the zero matrix.
This means exactly what ...
- 775
7
votes
0
answers
496
views
An algorithm to compute the number of paths of length at most k
So I had to answer the following question:
Given a graph $G = (V, E)$, and two vertices $v_i, v_j$, compute the number of walks between $v_i$ and $v_j$ of length at most $k$. $G$ is not too large, ...
- 445
1
vote
1
answer
1k
views
What is the advantage of a transformation matrix in perspective projection?
I was messing around with perspective projection. And it got me wondering whether using a perspective transformation matrix is the most efficient way. Because I also came up with another method which ...
- 119
10
votes
1
answer
564
views
Why does the log-rank conjecture use rank over the reals?
In communication complexity, the log-rank conjecture states that
$$cc(M) = (\log rk(M))^{O(1)}$$
Where $cc(M)$ is the communication complexity of $M(x,y)$ and $rk(M)$ is the rank of $M$ (as a matrix)...
- 10.2k
19
votes
4
answers
706
views
How to obtain the unknown values $a_i,b_j$ given an unordered list of $a_i-b_j\mod N$?
Can anyone help me with the following problem?
I want to find some values $a_i,b_j$ (mod $N$) where $i=1,2,…,K, j=1,2,…,K $ (for example $K=6$), given a list of $K^2$ values that correspond to the ...
- 193
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
19
votes
2
answers
629
views
Bigger picture behind the choice of matrices in the Strassen algorithm
In the Strassen algorithm, to compute the product of two matrices $\mathbf{A}$ and $\mathbf{B}$, the matrices $\mathbf{A}$ and $\mathbf{B}$ are divided into $2 \times 2$ block matrices and the ...
user4292
13
votes
0
answers
196
views
Complexity to compute the eigenvalue signs of the adjacency matrix
Let $A$ be the $n\times n$ adjacency matrix of a (non-bipartite) graph. Assume that we are given the amplitudes of its eigenvalues, i.e., $|\lambda_1|=a_1,\ldots, |\lambda_n|=a_n$, and we would like ...
- 1,346
11
votes
1
answer
786
views
How do database aggregations form a monoid?
On cs.stackexchange I asked about the algebird scala library on github, speculating on why they might need an abstract algebra package.
The github page has some clues:
Implementations of Monoids ...
- 568
3
votes
1
answer
333
views
What is this matrix column-selection problem, and how hard is it to approximate?
I ran across the following simple-to-state problem involving selection of a subset of columns simultaneously for a number of matrices. I suspect it might be well known, though I can't seem to place it....
- 575
2
votes
1
answer
401
views
All Pairs Shortest Path - Directed graph with integer weights
I don't understand how Distance Product works (or Min Plus Product). If we replace each argument in $A$ from $a_{i,j}$ to $x^{a_{i,j}}$ and each argument in $B$ from $b_{i,j}$ to $x^{b_{i,j}}$ and ...
- 241
19
votes
2
answers
1k
views
What is the space complexity of calculating Eigenvalues?
I am looking for a survey paper or a book covering results
about the space complexity of common linear algebra operations
such as matrix rank, eigenvalues calculation, etc.
I stress the "space ...
- 323
4
votes
2
answers
3k
views
Minimizing the maximum dot product among k unit vectors in an n-dimensional space
Suppose, we are given a set of $k$ unit vectors $v_1,\ldots,v_k$ in $\mathbb{R}^n$. Consider all possible dot products among distinct vectors $v_i \cdot v_j$, where $i \ne j$. Let,
$$\alpha = \max_{1 ...
- 1,591
8
votes
1
answer
7k
views
What is computational complexity of calculating the Variance-Covariance Matrix?
I am using a calculation of the Variance-Covariance matrix in a program I wrote (for Principal Component Analysis), and am wondering what the complexity of it is. While obviously the Eigenvector ...
- 183
1
vote
0
answers
186
views
Trace minimization with an orthogonality constraint
For positive semi-definite matrices $A,B$, how can I find an $X$ that minimizes $\text{Trace}(AX^TBX$) under the constraint:
that $X$ is orthogonal.
All the matrices have real entries and $A,B$ are ...
- 111
4
votes
0
answers
665
views
What about apply maxplus algebra for all-pairs shortest paths?
I didn't find deep informations on Wikipedia about all-pairs shortest path, in particular I do not know what is the best algorithm to solve this problem beyond Floyd-Warshall's one, then I do not know ...
10
votes
1
answer
425
views
What is the asymptotically fastest known algorithm for computing the nullspace of a matrix?
I know Gaussian Elimination takes $O(n^3)$ arithmetic operations, but I'm unsure if any better algorithms are known.
- 2,393
26
votes
1
answer
979
views
Complexity of matrix powering
Let $M$ be a square integer matrix, and let $n$ be a positive integer. I am interested in the complexity of the following decision problem:
Is the top-right entry of $M^n$ positive?
Note that the ...
- 497
17
votes
2
answers
436
views
similar matrices
Given two $n \times n$ matrices $A$ and $B$, the problem of deciding if there exist a permutation matrix $P$ such that $B = P^{-1}AP$ is equivalent to GI(Graph ...
- 1,281
8
votes
0
answers
139
views
Extension of Cheeger's inequality with distinguished vertices
The standard Cheeger's inequality for graph $G$ states that
$\frac{1}{2}$ $\lambda$ < $\phi(G)$ < $\sqrt{2\lambda}$
where $\lambda$ is the second smallest eigenvalue of the normalized ...
- 81
13
votes
1
answer
1k
views
Sampling from Multivariate Gaussian with Graph Laplacian (inverse) Covariance
We know from e.g. Koutis-Miller-Peng (based on work of Spielman & Teng), that we can very quickly solve linear systems $A x = b$ for matrices $A$ that are the graph Laplacian matrix for some ...
- 681
1
vote
0
answers
248
views
application for the Kchinchine inequality in Computer Science
The classical Kchinchine inequality states that for vector $a=(a_1, \ldots, a_{2m})\in R^{2m}$, for $p\geq 2$, and for independent Rademacher random variables $r_1, \ldots, r_{2m}$, one has
$$
E(|\...
- 11
-5
votes
1
answer
318
views
Solving a system of linear inequations
Consider the following system of inequalities:
$Ax=b$;
$x\geq 0$;
A is a $m\times n$ (non-square) and sparse matrix in which some part of entries are rational. a) How feasibility of this system can ...
- 253
15
votes
1
answer
384
views
Two matrices related by a permutation $B = P A P^T$ - complexity
What is computational complexity of the following problem:
given two complex $n\times n$ matrices $A$ and $B$ check if there is a permutation matrix $P$ such that:
$$B = P A P^T.$$
If it helps, one ...
- 625
19
votes
2
answers
1k
views
Linearly independent Fourier coefficients
A basic property of vector spaces is that a vector space $V \subseteq \mathbb{F}_2^n$ of dimension $n-d$ can be characterized by $d$ linearly independent linear constraints - that is, there exist $d$ ...
- 5,350
14
votes
1
answer
8k
views
The computational complexity of matrix multiplication
I am looking for information about the computational complexity of matrix multiplication of rectangular matrices. Wikipedia states that the complexity of multiplying $A \in \mathbb{R}^{m \times n}$ by ...
- 149
10
votes
1
answer
264
views
Boolean error correcting code over $\mathbb{F}_q$
Is there any known construction of a linear error correcting code $\mathsf{ECC}:\mathbb{F}_q^n \to \mathbb{F}_q^m$ (with reasonable parameters), such that when given a Boolean vector $v\in \{0,1\}^n$, ...
user887
3
votes
0
answers
80
views
Efficiently Detecting "edges" in the time frequency plane
Given a signal $y(t)\in\mathbb{R}$ I wish to detect edge patterns. $s(f,t)$ is a time-frequency decomposition of $y(t)$ in some window $(t-n,t+n)$ so that $f$ loosely corresponds to a local frequency....
- 131
4
votes
0
answers
394
views
Bounding the spectral radius of a sub-stochastic matrix
Suppose that I have a "sub-stochastic" matrix, namely, for an $n\times n$ matrix $A$ with nonnegative entries such that
for any $i$, $\sum_j a_{ij}\leq 1$ and there exists some $i$ with $\sum_j a_{ij}&...
- 109
9
votes
1
answer
641
views
Efficiently solve a system of strict linear inequalities with all coefficients equal to 1 without using a general LP solver?
Per the title, other than using a general purpose LP solver, is there an approach for solving systems of inequalities over variables $x_i, \ldots, x_k$ where inequalities have the form $\sum_{i \in I} ...
- 747
1
vote
0
answers
191
views
Complexity of checking whether linear equations have a positve solution [closed]
Consider a system of linear equations $Ax=0$, where $A$ is a $n\times n$ matrix with rational entries. Assume that the rank of $A$ is $<n$. What is the complexiy to check
whether it has a solution $...
- 109
3
votes
0
answers
157
views
Lower Bound Methods in NonDet Communication Complexity
rank+($M$) is the minimum $r$ such that the following statement holds.
The statement : there exists matrices $U,V$ such that $M = UV$ and $U$ has $r$ columns and $V$ has $r$ rows.
Is rank+($M$) ...
- 317
19
votes
3
answers
780
views
Complexity of deciding whether a matrix is totally regular
A matrix is called totally regular if all its square submatrices have full rank. Such matrices were used to construct superconcentrators. What is the complexity of deciding whether a given matrix is ...
- 2,878
11
votes
1
answer
469
views
Constructing vectors in general position
Let a real $k\times n$ ($k\le n$) matrix ${\bf A}$ with the property that any collection of $k$ columns is full rank.
Q: Is there an efficient way to deterministically find a vector ${\bf a}$ such ...
- 1,346
0
votes
0
answers
439
views
norms of compressible and incompressible vector
Let $a$ be a vector in $R^m$, such that $\sum_{i=1}^ma_i=0$
I would like to bound $\sqrt{2m(2m-1)}\|a\|_{\infty}$ by $\sqrt{2m}\|a\|_2$ (or other way arround with the sharp constants), in the case ...
- 1
2
votes
1
answer
112
views
Finding mapping between two spatial representations of the same objects
I have two matrices $U$ and $V$. $U$ is $n \times n$ and $V$ is $n \times m$. (Both are empirical results of an experiment.) I would like to find a linear transformation $A$, $m \times n$, such that $...
- 61
9
votes
2
answers
661
views
Midpoint solutions to linear programs
There is a linear program for which I want not merely a solution but a solution that's as central as possible on the face of the polytope that assumes the minimal value.
A priori, we expect the ...
- 1,206
18
votes
3
answers
2k
views
Determinant modulo m
What are the known efficient algorithms for computing a determinant of an integer matrix with coefficients in $\mathbb{Z}_m$, the ring of residues modulo $m$. The number $m$ may not be prime but ...
- 343
1
vote
1
answer
2k
views
What is the significance of abstract linear algebra in machine learning/computer vision research?
I am a computer science research student working in application of Machine Learning to solve Computer Vision problems.
Since, lot of linear algebra(eigen-values, SVD etc.) comes up when reading ...
- 161
13
votes
1
answer
542
views
Algorithmic Vector Problem
I have an algebraic problem related to vectors in the field GF(2).
Let $v_1, v_2, \ldots, v_m$ be (0,1)-vectors of dimension $n$, and $m=n^{O(1)}$. Find a polynomial time algorithm that finds a (0,1)-...
- 674
15
votes
1
answer
614
views
Log-space reduction from Parity-L to CNOT circuits?
Question.
In their paper Improved simulation of stabilizer circuits, Aaronson and Gottesman claim that simulating a CNOT circuit is ⊕L-complete (under logspace reductions). It is clear that it ...
- 8,821
12
votes
2
answers
390
views
On $n$ dimensional manifolds and lattices
I'm looking for the proof of Theorem 4 that appears in this paper:
An Infinite Hierarchy of Intersections of Context-Free Languages by Liu and Weiner.
Theorem 4: An $n$-dimensional affine manifold is ...
- 3,280
16
votes
1
answer
1k
views
Solving a linear diophantine equation approximately
Consider the following problem:
Input: a hyperplane $H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\}$, given by a vector $\mathbf{a} \in \mathbb{Z}^n$ and $b \in \mathbb{Z}$ in ...
- 18.1k
7
votes
1
answer
271
views
determining if a matrix of linear forms represents a non-degenerate matrix
Let $k$ be a field with $p$ elements. Consider the following computational problem
Input: a natural number $n$, $n^2$ linear forms $M_{ij}$, $i,j=1,\ldots n$ in $n^2$ variables $X_{11}, \ldots X_{...
- 301
7
votes
0
answers
135
views
Reference request: reducing rank computations to characteristic polynomials over arbitrary rings
Question. I'm looking into certain algorithms for linear algebra which lie in NC2. Does anyone know of alternative references for the proof of the proposition just below, relating rank of matrices ...
- 8,821
16
votes
4
answers
3k
views
Definition of matrix-multiplication exponent $\omega$
Colloquially, the definition of the matrix-multiplication exponent $\omega$ is the smallest value for which there is a known $n^{\omega}$ matrix-multiplication algorithm. This is not acceptable as a ...
- 3,488
7
votes
1
answer
378
views
Complexity to calculate a full set of eigenvectors over a finite field
Let a full rank $n\times n$ matrix ${\bf A}$ with elements over $\mathbb{GF}(2)$. What is the worst case complexity to calculate $n$ linearly independent (over $\mathbb{GF}(2)$) vectors, such that ...
- 1,346
19
votes
1
answer
934
views
Is solving systems of equations modulo $k$ in $\mathsf{coMod}_k\mathsf L$ for $k$ composite?
I'm interested in the complexity of solving linear equations modulo k, for arbitrary k (and with a special interest in prime powers), specifically:
Problem. For a given system of $m$ linear equations ...
- 8,821
10
votes
1
answer
596
views
Can such a matrix exist?
During my work i came up with the following problem:
I am trying to find an $n \times n$ $(0,1)$-matrix $M$, for any $n > 3$, with the following properties:
The determinant of $M$ is even.
For ...
- 615
11
votes
0
answers
2k
views
Complexity of finding the leading eigenvector of a graph Laplacian
Let ${\bf L}$ be the $n\times n$ Laplacian of a graph. What is the worst case complexity for calculating the maximum eigeinvector of ${\bf L}$?
Are there any families of Laplacians for which it takes ...
- 1,346