Questions tagged [linear-algebra]
Linear algebra deals with vector spaces and linear transformations.
227
questions
2
votes
1
answer
145
views
Recovering a rank-one matrix from its eigendecomposition after randomized rounding
Let $A = xy^T$ be a rank-$1$ matrix, and suppose every entry of $A$ is in $[0,1]$. We can create a binary matrix $A_{\rm rounded}$ by setting
$$ [A_{\rm rounded}]_{ij} = \begin{cases} 1 & \mbox{ ...
- 185
6
votes
1
answer
701
views
What are the consequences of solving XOR 3-SAT in Logspace?
XOR Formulas
Consider boolean formulas with connectives $\wedge$ (AND) and $\oplus$ (XOR). Such a boolean formula is a valid instance for XOR SAT if it is a conjunction of $\oplus$-clauses. An $\...
- 5,127
2
votes
0
answers
69
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 ...
- 596
2
votes
0
answers
98
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 ...
- 21
11
votes
1
answer
261
views
Binary vector $t$ in $span(S)$ over $\mathbb{Z}/q\mathbb{Z}$ for all prime powers $q$ $\Rightarrow$ $t$ in $span(S)$ over $\mathbb{Z}$?
I have a set of $n$ binary vectors $S = \{s_1, \ldots, s_n \} \subseteq \{0,1\}^k \setminus \{1^k\}$ and a target vector $t = 1^k$ which is the all-ones vector.
Conjecture: If $t$ can be written as ...
- 5,255
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
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
6
votes
1
answer
276
views
Algebraic account of Gaussian elimination?
For fun, I've been looking at the interpretation of linear logic in terms of finite-dimensional vector spaces, and ran into an interesting
question about the interpretation of double-negation-...
- 32.4k
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
0
votes
1
answer
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)$...
- 12.8k
-1
votes
1
answer
121
views
given a set of $n$ points in $d$-dimensional space and the basis vectors of some subspace, how to find all the points on that space?
given a set $A$ of $n$ points with integer coordinates in $\mathbb{R}^d$, and $k<d$ basis vectors of a subspace $K$ of $\mathbb{R}^d$, is there an efficient algorithm that returns all points from $...
2
votes
1
answer
95
views
Some consequences of the Roychowdhury-Orlitsky-Siu result from 1994
This pertains to the proof of theorem 1.1 in this paper, http://dl.acm.org/citation.cfm?id=2897636
So Roychowdhury-Orlitsky-Siu had shown that the number of depth $2$ linear threshold gate circuits ...
- 1,443
2
votes
0
answers
67
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 ...
- 1,224
3
votes
1
answer
109
views
About the sign-rank of the Minsky-Pappert function
Apologies this might be a very trivial thing I am getting confused by!
Firstly in corollary 1.1 (page 3) in this paper, https://eccc.weizmann.ac.il/report/2016/075/ the authors claim that they have ...
- 1,443
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
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
1
vote
1
answer
341
views
"Linear" hashing function
Say we have two chunks of data $X$ and $Y$, which may be of different sizes, is there a non-trivial function $hash$, and operation $*$, such that:
$$hash(X+Y) = hash(X) * hash(Y)$$
...where $+$ is ...
- 131
7
votes
1
answer
185
views
Rank-robustness of the parallel complexity of linear algebra problems
It is known that most computational problems related to linear algebra
can be computed in $NC^2$ - i.e. for an $n\times n$ matrix $A$, over the reals
or a finite field, we can compute the rank of $A$, ...
- 1,224
1
vote
0
answers
126
views
Can we make a matrix stable by changing its upper-left submatrix?
A matrix $A$ is called strictly stable if its eigenvalues have negative real parts. Given a matrix $A \in \mathbb{R}^{n \times n}$, suppose we can change its upper-left $k \times k$ submatrix at will (...
- 11
1
vote
1
answer
150
views
Why are folded Reed Solomon Codes considered non linear?
This is for my understanding. What am I missing?
- 395
7
votes
1
answer
267
views
Using an oracle to find a vector $b$ for which $Ax=b$ has a solution
There is an oracle built around a hidden $m\times n$ matrix $A$ all of whose entries are 0 or 1, where $m>n$. The oracle takes as input an integer vector $b$ with positive entries, and answers as ...
- 233
1
vote
0
answers
141
views
Non-backtracking paths and the zeta function of graphs
This question has also been posted on mathSE here: https://math.stackexchange.com/questions/2215888/non-backtracking-paths-and-the-ihara-zeta-function
For a connected $d$-regular graph $G=(V,E)$ with ...
- 383
3
votes
0
answers
97
views
Complexity of Underdetermined Systems [closed]
Given a field $\mathbb{F}$ and a consistent underdetermined system $Ax=b$ over $\mathbb{F},$ $A\in \mathbb{F}^{m \times N}$ and $b \in \mathbb{F}^m,$ finding a vector $z \in \mathbb{F}^N$ such that $...
- 131
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
15
votes
1
answer
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$.
- 3,950
15
votes
2
answers
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'...
- 253
8
votes
2
answers
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 ...
- 1,224
10
votes
1
answer
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 ...
7
votes
1
answer
407
views
Number of solutions for a system of linear equations over a finite ring
Let $R$ be a finite ring with operations $(+,\cdot)$. Let $A \in R^{m\times n}$ and
$b\in R^{m}$.
Questions:
What is the complexity of counting the number of solutions to the system of equations $...
1
vote
0
answers
145
views
Fourier expansion of boolean functions and affine subspaces
Let $f:\mathbb{F}^n_2\rightarrow \{0,1\}$ be a function constant on an affine subspace $V$ of co-dimension $t$. Assume that that $V$ is a linear subspace, by replacing $f(x)$ with $f(x+v)$ for some $v ...
- 31
8
votes
2
answers
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?
- 3,950
12
votes
2
answers
3k
views
Memory requirement for fast matrix multiplication
Suppose we want to multiply $n \times n$ matrices. The slow matrix multiplication algorithm runs in time $O(n^3)$ and uses $O(n^2)$ memory. The fastest matrix multiplication runs in time $n^{\omega + ...
- 3,488
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
4
votes
1
answer
199
views
How well do subspaces hit sets
Let $S\subset F_2^n$ be a subset of size $\epsilon\cdot 2^n$.
Say I choose a random subspace $V$ of dimension $k$ in $F_2^n$.
I want to know what is the smallest $k$ such that $V$ `hits' $S$, i.e., $V\...
- 209
3
votes
2
answers
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 ...
- 3,243
6
votes
1
answer
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 ...
- 73
1
vote
1
answer
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 ...
- 653
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
1
vote
0
answers
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$?
- 73
4
votes
2
answers
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 ...
- 653
2
votes
0
answers
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 ...
- 653
2
votes
1
answer
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 ...
- 727
1
vote
1
answer
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 ...
- 639
13
votes
4
answers
1k
views
Finding the sparsest solution to a system of linear equations
How hard is it to find the sparsest solution to a system of linear equations?
More formally, consider the following decision problem:
Instance: A system of linear equations with integer coefficients ...
- 5,127
7
votes
1
answer
881
views
Finding the number of independent rows of a matrix
There is a $n\times n$ matrix $A$, and we are asked to find the number $N(A)$ of independent rows in it, i.e. rows that are not a linear combination of the other rows. Clearly, if $rank(A)=n$, then $N(...
- 243
6
votes
2
answers
2k
views
Min Hamming distance of a given string from substrings of another string
Let $U$ be a small finite set.
Consider the following problem:
Input: two strings $u \in U^k$ and $v\in U^n$ with $k \leq n$.
Output: a (contiguous) substring of $v$ of length $k$
with the minimum ...
- 113
2
votes
0
answers
257
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 ...
- 253
0
votes
1
answer
225
views
Graph isomorphism problem with invertible adjacency matrices
This question is supplementary to the question asked here.
One of the answers give a class of graphs for which the adjacency matrices are invertible which is defined as follows.
Given a ...
- 653
2
votes
0
answers
76
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 ...
- 89
2
votes
0
answers
62
views
How to compute the basis
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{...
- 89