Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [linear-algebra]

Linear algebra deals with vector spaces and linear transformations.

1
vote
0answers
61 views

Missing proof in Salil Vadhan's monograph on pseudorandomness, Random Walks and S-T Connectivity

In Salil Vadhan's monograph on pseudorandomness, chapter 2, half of the proof of Lemma 2.51 is missing http://people.seas.harvard.edu/~salil/pseudorandomness/power.pdf . I don't state the full lemma ...
10
votes
0answers
110 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 ...
8
votes
2answers
247 views

Non-Orthogonal Vectors Problem

Consider the following problems: Orthogonal Vectors Problem Input: A set $S$ of $n$ Boolean vectors each of length $d$. Question: Do there exist distinct vectors $v_1$ and $v_2 \in S$ ...
2
votes
1answer
111 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{ ...
6
votes
1answer
203 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 $\...
2
votes
0answers
52 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
71 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 ...
11
votes
1answer
202 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 ...
12
votes
1answer
273 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-...
0
votes
0answers
67 views

Why do spectral ultrasparsifiers need to be trees

Given a graph $G$ with $n$ vertices and $m$ edges, a $(\kappa,h)$-ultra-sparsifier $H$ is a graph on the same set of vertices such that: [1] $H$ consists of a spanning tree $T$ along with $\frac{hm}{\...
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 ...
6
votes
1answer
201 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-...
5
votes
0answers
103 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 $$\...
-1
votes
1answer
59 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 $...
1
vote
1answer
78 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 ...
2
votes
0answers
58 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 ...
3
votes
1answer
82 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 ...
5
votes
0answers
72 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 ...
26
votes
0answers
440 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 ...
1
vote
1answer
246 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 ...
8
votes
1answer
171 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
vote
0answers
92 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 (...
1
vote
1answer
114 views

Why are folded Reed Solomon Codes considered non linear?

This is for my understanding. What am I missing?
8
votes
1answer
238 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 ...
1
vote
0answers
80 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 ...
4
votes
0answers
76 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 $...
4
votes
0answers
122 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 ...
15
votes
1answer
433 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$.
15
votes
2answers
410 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'...
8
votes
2answers
555 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 ...
10
votes
1answer
230 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 ...
6
votes
1answer
185 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
0answers
62 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 ...
7
votes
2answers
312 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?
12
votes
2answers
631 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 + ...
0
votes
0answers
104 views

Optimization of function on the Eigenvector of symmetric Matrices

My problem is like that, I want to use some function, say $f$ on the principal eigenvector(PEV), $X_1 \in R^n$ of an adjacency matrix, $A \in R^{n \times n}$, of a simple undirected and unweighted ...
4
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 ...
4
votes
1answer
148 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\...
3
votes
2answers
427 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 ...
7
votes
1answer
214 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
1answer
60 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 ...
17
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 ...
1
vote
0answers
123 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$?
3
votes
2answers
113 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 ...
3
votes
0answers
87 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 ...
3
votes
1answer
333 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
1answer
115 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 ...
13
votes
4answers
755 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 ...
7
votes
1answer
379 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(...
3
votes
2answers
718 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 ...