Questions tagged [linear-algebra]
Linear algebra deals with vector spaces and linear transformations.
93
questions with no upvoted or accepted answers
26
votes
0
answers
697
views
Rank mod 6 vs rank over the reals
Let $A$ be a boolean matrix (eg with $0,1$ entries). Assume that $A$ has rank $\le r$ both over $\mathbb{F}_2$ and over $\mathbb{F}_3$. Does this imply that $A$ has low rank over the reals? This seems ...
- 756
15
votes
0
answers
389
views
Complexity of approximating the range of a matrix
Given an $m$ by $n$ matrix $M$ with $m \leq n$ and elements from $\{-1,1\}$, let us define:
$$S_M = |\{Mx : x \in \{-1,1\}^n\}|.$$
I believe that it is NP-hard to compute $S_M$ exactly, by applying ...
- 3,950
14
votes
0
answers
615
views
Approximation algorithm for Minimum Fill-In and/or minimum elimination ordering (for directed graphs)
Recently while working on a problem, I had to go through some of the literature on nested dissection. I happen to have one (maybe two?) questions related to the same.
First, I will define a few ...
- 1,953
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
12
votes
0
answers
267
views
the largest element of a matrix product
Given two matrices, I'm interested in finding the largest element of their product. I wonder if it's possible to do it significantly faster than the matrix multiplication the solution seems to require?...
- 231
11
votes
0
answers
208
views
Do Banach spaces and linear contraction maps form a model of ILL with an exponential?
Recently, I read on the nLab that the category of Banach spaces and linear contractions is small complete, small cocomplete, and monoidal closed.
This means that Banach spaces and short linear maps ...
- 32.4k
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
11
votes
1
answer
375
views
Is there a P-complete problem on diophantine equations?
In general deciding whether a diophantine equation has any integer solutions is equivalent to the halting problem. I believe that deciding if a quadratic diophantine equation has any solution is NP-...
- 111
10
votes
0
answers
169
views
Number of graphs with prescribed spectrum
I have a question relevant to the number of graphs with prescribed spectral ratio.
Let $A$ be the adjacency matrix of a graph on $n$ vertices. Let $\lambda_i$ be its $i$-th largest (signed) eigenvalue....
- 1,346
10
votes
1
answer
494
views
Finding a cutting plane that splits a polyhedron evenly
Say we have a polyhedron in standard form:
\begin{equation*}
\begin{array}{rl}
\mathbf{A}\mathbf{x} = \mathbf{b} \\\\
\mathbf{x} \ge 0
\end{array}
\end{equation*}
Are there any known methods for ...
9
votes
0
answers
337
views
Extensions of Affine Dispersers
A function $f\colon\{0,1\}^n\to\{0,1\}$ is called an affine disperser for dimension $d$, if for every affine subspace $S\subseteq \{0,1\}^n$ of dimension at least $d$, $f$ is not constant on $S$. This ...
- 2,247
9
votes
0
answers
570
views
Finding SVD efficiently for $AB^T$
I have a low rank matrix given as $AB^T$ where $A,B \in \mathbb{R}^{n \times p}$ and $p \ll n$. (I know $A$ and $B$ separately)
EDIT: (I have added the second question here since it was closed as a ...
user4292
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
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
7
votes
0
answers
254
views
Reference for computing the rank of a matrix in polynomial time
In a recent paper, I need to use the fact that computing the rank of a matrix over the integers has polynomial complexity. Given the context, I don't particularly care about the exact asymptotics, as ...
- 171
7
votes
0
answers
179
views
Algebraic methods for testing planarity
Mac Lane's planarity criterion states that a graph is planar if and only if it has a cycle basis such that each edge is contained in at most two cycles, we call such a basis a 2-basis. A 2-basis of a ...
- 215
7
votes
0
answers
460
views
Gaussian elimination for inverting matrices modulo prime power
Can I use Gaussian elimination to compute matrix inverse over the ring $\mathbb{Z}_{p^k}$ (ring of residues modulo $p^k$) where $p$ is prime and $k$ is an integer greater than $1$?
Such matrix is ...
- 71
7
votes
0
answers
370
views
Spectral Graph Theory and Matroid Theory
I have just started grad school this year and I have been into Spectral Graph Theory for some time now. Recently I got introduced to Matroid Theory and although I know the field has been around for ...
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
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
7
votes
0
answers
207
views
Are the minimal quantum and classical span programs the same?
A span program is a linear-algebraic way of specifying a boolean function introduced here which has found recent application in quantum query complexity.
A span program for a function $f: \{0,1\}^n \...
- 10.2k
7
votes
0
answers
140
views
What's new in sparse eigensystems solution
As a part of other work I need to solve relatively large (~1E5x1E5) and sparse (~100 non-zero elements in each raw in few blocks) hermitian eigensystems. Usually only few eigenvalues+vectors are ...
- 171
6
votes
0
answers
191
views
An optimal subspace projection problem
Suppose we have a $k$-dimensional subspace $V$ in $\mathbb{R}^n$ given by a basis $\{v_1,\cdots,v_k\in \mathbb{R}^n\}$, find an index set $I\subset [n]$ with $|I|=m$ where $k\le m\le n$, such that
$$\...
- 271
6
votes
0
answers
237
views
What is the space complexity of computing the eigenvectors of a matrix?
By the answer to this question, computing the eigenvalues of a matrix to within $2^{-n}$ precision can be done in polylogarithmic space. Is it also possible to compute the eigenvectors of a matrix to ...
- 161
5
votes
0
answers
78
views
Hardness result or reference for optimal Gaussian elimination process
I'm wondering if the following problem is NP-Complete or has any hardness result.
References on related problem are also welcome.
Input: integers $n\geq1,k\geq0$ and an invertible matrix $M\in\mathbb ...
- 101
5
votes
0
answers
218
views
Is there a fast algorithm for inverting a sparse matrix?
I am doing research on a random-walk like problem. As a critical part of my solution, I need to invert a non-singular sparse matrix of size $n \times n$ and with $O(n)$ non-empty entries. I'm working ...
- 235
5
votes
0
answers
125
views
Completing a matrix (over the reals) to be singular
Consider the following problem: you are given a matrix (say, with rational entries) some of whose entries are actually left blank; can these blanks be filled in with real numbers so that the resulting ...
- 51
5
votes
0
answers
159
views
Reconstruction of sparse vectors from random matrices
In the paper [A], the following linear algebra result (Lemma 5 in [A]) is stated as being well known. Note that a vector is $s$-sparse if it contains at most $s$ non-zero entries.
Lemma: Let $1 \...
5
votes
0
answers
131
views
Tools to bound the singular values of a finite sum of random matrices from below?
Matrix Chernoff bounds (see also this arXiv paper) are usually used to give upper bounds on the largest eigenvalue of a finite sum of random matrices. Sometimes it can also be used to give a lower ...
- 179
5
votes
0
answers
297
views
Hardness of finding eigenvalues?
Is there a setting in which finding eigenvalues/eigenvectors is computationally hard? Or at least, not known to be computationally easy?
For example, how computationally hard or easy is it to find ...
- 331
5
votes
0
answers
137
views
Integer multiplication where regular Fourier Transform approach would fail to provide best upper bound
I have a problem where multiplication of integers via regular Fourier Transform based multiplication technique would fail to provide best upper bound since the sequences of bits in both integers are ...
- 12.8k
4
votes
0
answers
127
views
Boolean matrix $M$ with Boolean rank $r$ but real rank $2^r$
$\newcommand{\F}{\mathbb{F}}\newcommand{\R}{\mathbb{R}}$
Question is in the title basically: does there exist a Boolean matrix $M$ where $\operatorname{rank}_{\F_2}(M)=r$ but $\operatorname{rank}_{\R}(...
- 51
4
votes
0
answers
68
views
Precise rank of a sparse integer matrix
Consider a large sparse rectangular integer matrix. Is there a way to compute its exact rank that is better in terms of speed and/or memory usage compared to a dense matrix?
4
votes
0
answers
112
views
efficiently computing a sum of products of polynomials
Let $F$ be a prime finite field. Let $d$ be a power of two dividing $p-1$. Suppose I have $d$ pairs of univariate polynomials $f_i,g_i$ over $F$ for $i=1,\ldots,d$. All have degree less than $d$.
I ...
- 209
4
votes
0
answers
89
views
Complexity of Encoding a Matroid Flow Problem in a Matrix
Context:
Take a directed graph $G$ with a specified subset of source vertices $S$ and target vertices $T$.
We say a subset $I\subseteq T$ of size $r$ is independent if there exist $r$ distinct ...
- 576
4
votes
0
answers
88
views
About Boolean functions with a high sign-rank
Recently in this beautiful paper, https://arxiv.org/pdf/1705.02397.pdf it has been shown that there is an explicit $Th \circ Th$ function with sign-rank scaling exponentially in dimension. I wanted to ...
- 1,443
4
votes
0
answers
108
views
Rigid families of $\{0,1\}$ matrices
We know that there are many families of matrices over $\Bbb F_q$, $\Bbb R$ etc are rigid.
See http://mahdi.cheraghchi.info/talks/rigidity_talk.pdf
Do we know there are many families of rigid REAL ...
- 12.8k
4
votes
0
answers
171
views
Extensions of Sylvester's inertia law?
Sylvester's inertia law deals with the signatures of quadratic forms. I was thinking that it may be possible to extend this to multilinear forms; here is a first attempt.
Let $M$ be a $k$-linear form ...
- 1,292
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 ...
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
3
votes
0
answers
67
views
Minimizing a sum of thresholded quadratics
Let $W_1, \ldots, W_k$ be positive semi-definite matrices, $b_1, \ldots, b_k$ be vectors, and $a_1, \ldots a_k$, $c_1, \ldots, c_k$ be scalars. How difficult is it to find an approximate minimum of
...
- 31
3
votes
0
answers
132
views
Given a matrix $A$ maximize the number of positive elements in $Ax$ under specific constraints for $x$
Let $A = [a_{ij}]$ be a symmetric matrix with nonnegative values and $k << n/2$ a given constant. We want to rearrange the columns of the matrix such that the number of rows with the following ...
- 31
3
votes
0
answers
147
views
Testing for satisfiability of a system of linear equations over GF(2)
Consider a system linear equations in $x$, $Ax =b$, where A is an $n\times n$ matrix, and $b$ is a column vector, and all operations are over $GF(2)$.
Is it easier to check satisfiability of the ...
- 271
3
votes
0
answers
243
views
Complexity of eigenvalue problem
Many matrix diagonalization algorithms have time complexity $\mathcal{O}(n^3)$ where $n$ is the number of columns/raws (consider only square matrices).
What is the best time lower bound it is known?
...
- 531
3
votes
0
answers
252
views
efficient data structures for generalized tensor products
The usual tensor product of vectors is a matrix. There has been tons of research into efficiently storing and operating on matrices in computers.
But we can generalize the tensor product quite a bit....
- 1,063
3
votes
0
answers
179
views
Algorithm (parallel and serial) for Gram-Schmidt
Suppose we are given $m$ vectors $v_1, \dots, v_m$ in $n$-dimensional space $\mathbf R^n$ (or perhaps they are specified up to $b$ bits of precision). I would like to find an orthonormal basis for the ...
- 3,488
3
votes
0
answers
197
views
An interesting construction of a Tits building?
The notion of Tits building was introduced by Jacques Tits to study certain questions in group theory. The wikipedia entry gives a way to construct a Tits building from a vector space, but I would be ...
- 1,292
3
votes
0
answers
102
views
Finding the closest subspace to a collection of subspaces
Suppose we have a collection of linear subspaces $\mathbb{C}$ lying in $\mathbb{R}^d$, such that each $c \in \mathbb{C}$ is of dimension at most $k \leq d$ for a given fixed $k$ and $|\mathbb{C}| = n$....
- 729
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
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