# Questions tagged [linear-algebra]

Linear algebra deals with vector spaces and linear transformations.

79 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
520 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 ...
360 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 ...
504 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 ...
187 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 ...
196 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 ...
322 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-...
137 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 ...
162 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....
445 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 ...
538 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 ...
284 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 ...
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}$ ...
136 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 ...
141 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 ...
383 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 ...
331 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, ...
131 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

200 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 ...
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 ...
153 views

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 ...
125 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 ...
136 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 ...
162 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? ...
222 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....
153 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 ...
179 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 ...
86 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$....
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....
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$) ...
326 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 ...
58 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 ...
88 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 ...
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 ...
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 ...