Questions tagged [linear-algebra]

Linear algebra deals with vector spaces and linear transformations.

75 questions
476 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 ...
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 ...
492 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 ...
177 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 ...
192 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?...
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 ...
126 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 ...
160 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....
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 ...
280 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 ...
188 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}$ ...
129 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 ...
378 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 ...
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, ...
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 ...
193 views

157 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 ...
107 views

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 $$\... 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 ... 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 \... 0answers 115 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 ... 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 ... 0answers 75 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 ... 0answers 106 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 ... 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 ... 0answers 524 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 ... 0answers 381 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}&... 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 ... 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 ... 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 ... 0answers 133 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? ... 0answers 207 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.... 0answers 135 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 ... 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 ... 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.... 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.... 0answers 150 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) ... 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 ... 0answers 53 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 ... 0answers 79 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 ... 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 ... 0answers 94 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 ... 0answers 170 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 ... 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 ...
Given $n$ sets of linear constraints $\Theta_1, \cdots, \Theta_n$ which are over $\vec{x}_1, \cdots, \vec{x}_n$ respectively where $\vec{x}_i$ and $\vec{x}_j$ are pairwise disjoint, and \$W= \begin{...