# Questions tagged [linear-algebra]

Linear algebra deals with vector spaces and linear transformations.

227 questions
Filter by
Sorted by
Tagged with
145 views

41 views

### Decomposing outer product or general rank factorization over $\Bbb F_q$

Given matrix $M\in\Bbb F_q^{n\times n}$ with the promise that there are two matrices $A\in\Bbb F_q^{n\times 1}$ and $B\in\Bbb F_q^{1\times n}$ such that $AB=M$ is there a deterministic $O((n\log q)^c)$...
121 views

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 ...
3k views

### The minimum number of arithmetic operations to compute the determinant

Has there been any work on finding the minimum number of elementary arithmetic operations needed to compute the determinant of an $n$ by $n$ matrix for small and fixed $n$? For example, $n=5$.
538 views

### Status of Raghavendra's algorithm for solving linear systems in finite fields

In 2012, Lipton wrote a blog entry about a new algorithm for solving linear systems over finite fields by Prasad Raghavendra. The link to Raghavendra's draft paper on the topic is now dead, and I can'...
945 views

### Dichotomy of the spectra of directed graphs

Compared to spectra of undirected graphs, which correspond to symmetric matrices, the spectra of directed graphs is not very well known: It is known that a directed graph $G = (V,E)$ has an adjacency ...
288 views

### Complexity of reachability in linear dynamical systems over finite fields

Let $A$ be a matrix over the finite field $\mathbb{F}_2 = \{0,1\}$ and $x$, $y$ be vectors of the space $\mathbb{F}_2^n$. I am interested in the computational complexity of deciding whether there ...
407 views

948 views

### Estimating the rank of a large sparse matrix

Consider a large sparse n by n matrix. Are there any methods to estimate its rank in time roughly proportional the number of elements in the matrix?
3k views

564 views

### Quantum complexity of maximum inner product search

Given two matrices $X \in \mathbb{R}^{m \times k}$, $Y \in \mathbb{R}^{n \times k}$, maximum inner product search (MIPS) asks for the largest $l$ entries of $X Y^T$. Typically $k \ll m, n$ (many ...
224 views

### Checking properties of matrices

Given a sparse matrix $A$ in $\mathbb{Z}^{n\times n}$, how easily could one check whether a coefficient $\alpha_k$ of the characteristic polynomial $P_A$ of $A$ is equal to $0$ (without the need to ...
1 vote
100 views

### How the hardness of hidden subgroup problem in $S_n$ changes as the order of the subgroup grows?

In Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al. In this paper it is showed that no hidden subgroup algorithm can distinguish the trivial ...
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 ...
1 vote
180 views

### How to efficiently generate a random 0-1 matrix of a given rank

How to efficiently generate a random $n\!\times\!n$ $0$-$1$ matrix of rank $k<n$?
219 views

### Is there any hidden subgroup of a symmetric group which can be efficiently determined?

There have been a number of cases where efficient hidden subgroup algorithms have been found for specific non-Abelian groups with very specific structures. Why haven't we found any efficient quantum ...
123 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 ...
488 views

### Matrix multiplication with transpose

Let $A,B\in\mathbb{F}^{n\times n}$ be two $n\times n$ matrices over the underlying field $\mathbb{F}$. In addition, $A$ is guaranteed to be a symmetric matrix, i.e, $A=A^{T}$. We assume complexity ...
1 vote
145 views

### Low rank approximation of matrix under $l_2$ norm

Theorem 14 of this paper by Tam´as Sarl´os gives a relative error rank-$k$ approximation of a given matrix $A$ under the frobenius norm. I am looking for reference of a similar result (relative error ...