Questions tagged [linear-algebra]

Linear algebra deals with vector spaces and linear transformations.

76 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
26
votes
0answers
486 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 ...
16
votes
0answers
359 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 ...
14
votes
0answers
493 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 ...
13
votes
0answers
182 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 ...
11
votes
0answers
193 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?...
11
votes
0answers
1k 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 ...
11
votes
1answer
291 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-...
10
votes
0answers
131 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 ...
10
votes
0answers
161 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....
10
votes
1answer
418 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
0answers
536 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 ...
8
votes
0answers
282 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 ...
8
votes
0answers
189 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}$ ...
8
votes
0answers
132 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 ...
7
votes
0answers
380 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 ...
7
votes
0answers
323 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, ...
7
votes
0answers
130 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 ...
7
votes
0answers
193 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 \...
7
votes
0answers
133 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 ...
6
votes
0answers
192 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 ...
6
votes
0answers
266 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 ...
5
votes
0answers
51 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\...
5
votes
0answers
163 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 ...
5
votes
0answers
107 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 $$\...
5
votes
0answers
119 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 ...
5
votes
0answers
151 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
0answers
116 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 ...
5
votes
0answers
261 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 ...
4
votes
0answers
77 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 ...
4
votes
0answers
107 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 ...
4
votes
0answers
169 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 ...
4
votes
0answers
534 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
0answers
384 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}&...
3
votes
0answers
65 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 ...
3
votes
0answers
123 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 ...
3
votes
0answers
134 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 ...
3
votes
0answers
140 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? ...
3
votes
0answers
210 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....
3
votes
0answers
136 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
votes
0answers
177 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 ...
3
votes
0answers
85 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$....
3
votes
0answers
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....
3
votes
0answers
152 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$) ...
3
votes
0answers
323 views

Taking Square Roots of Matrices over Z/nZ

Is it easy (computationally) to take square roots of matrices over Z/nZ, if you know the factorization of n? More specifically, suppose I generate a random matrix M, and square it. Can a ...
2
votes
0answers
57 views

Which invertible linear transformations can be computed reversibly without ancilla/garbage bits just as easily as they can be computed irreversibly?

Suppose that $L:F_{2}^{n}\rightarrow F_{2}^{n}$ is an invertible linear transformation. Then define $w(L)$ to be the gate count of the smallest reversible circuit on $n$ bits without ancilla/garbage ...
2
votes
0answers
80 views

Why is triangle inequality needed for indexing?

Maybe this is a silly question but I actually can't fulfill that by myself. I'm reading some papers about similarity metrics and I always find that for a distance function $d$ the triangle inequality ...
2
votes
0answers
59 views

A random ensemble of sparse boundary operators

The following question arises from the study of quantum error correction, and high-dimensional expanders: Is there an algorithm that for given numbers $n>0,d≤n,r≤n$ samples uniformly a linear ...
2
votes
0answers
95 views

Why hidden subgroup problem is easy for very large subgroup?

I am going through QUANTUM MECHANICAL ALGORITHMS FOR THE NONABELIAN HIDDEN SUBGROUP PROBLEM by Grigni et al. On page 2, it is said that solving the hidden subgroup problem becomes very easy when the ...
2
votes
0answers
172 views

Inclusion of polytopes

Consider the following two system of linear (in)eqaulities: $S = Ax \leq b;\; Cx = e$ $T = Dx \leq d;\; Gx = g$ How can I check if $S\cap \neg T=\emptyset$ where $\neg T$ is the complement of the ...
2
votes
0answers
70 views

Check whether a point is a vertex of Minkowski sum of polytopes

Given $n$ polytopes $$\begin{align*} P_1&=\{(f^1_1(\vec{x}_1), \cdots, f^1_m(\vec{x}_1))\mid A_1\vec{x}_1\leq b_1\}\\ P_2&=\{(f^2_1(\vec{x}_2), \cdots, f^2_m(\vec{x}_2))\mid A_2\vec{x}_2\leq ...