Questions tagged [linear-algebra]
Linear algebra deals with vector spaces and linear transformations.
188
questions
-3
votes
1answer
42 views
Finding a non-negative solution to an integer system of linear equations
Let $A$ be an $n \times m$ integer matrix and consider the system of equations $Ax = b$ where $b$ is an integer vector. I want to find a solution $x$, assuming one exists, such that the components of $...
7
votes
1answer
122 views
The complexity of the permanent of low rank matrices
I know that for an arbitrary $n \times n$ matrix, Ryser's algorithm can compute the permanent in $\mathcal{O}(2^n n^2)$ time. I'm interested in computing the permanent of $n \times n$ matrices of rank ...
7
votes
0answers
136 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 ...
4
votes
2answers
157 views
What are some good resources for strengthening my theoretical foundation for machine learning?
I'm a computer science major and I'm taking a lot of machine learning courses. I'm finding that my theoretical foundation on subjects like calculus and linear algebra are not as strong as I'd like ...
40
votes
3answers
5k views
Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time
It is commonly believed that for all $\epsilon > 0$, it is possible to multiply two $n \times n$ matrices in $O(n^{2 + \epsilon})$ time. Some discussion is here.
I have asked some people who are ...
2
votes
1answer
146 views
Finding whether $n$ polytopes have nontrivial intersection from pairwise comparisons
I have a set of $n$ convex polytopes of the form
$$\mathcal{L_i} = \{ \beta \mid C_i \beta \leq 0 \}$$
where $C$ is a matrix and $\beta$ is a vector. I know that for each pair of polytopes $$(\...
0
votes
0answers
59 views
s,t-Graphs representing infinite number of addition chains
I am looking at directed acyclic multi-graphs $G=(V,E)$ with a single source and sink with integer labeled arcs. Each vertex has exactly two inputs except $s$. Each vertex has at least one output ...
1
vote
0answers
49 views
Underlying codes in Niederreiter cryptosystems
Niederreiter cryptosystem is usually described by a parity check matrix $H$ over $\mathbb{F}_{2^n}$.
The minimum distance $d$ is given by
$d= min\lbrace k \text{ such that there are $k$ linearly ...
5
votes
0answers
55 views
Hardness result or reference for optimal Gaussian elimination process
I'm wondering if the following problem is NP-Complete or has any hardness result.
References on related problem are also welcome.
Input: integers $n\geq1,k\geq0$ and an invertible matrix $M\in\...
5
votes
0answers
195 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 ...
0
votes
0answers
21 views
Does optimal fitting flat must pass through the mean of the point set?
I am confused about a statement made in the paper Linear Time Algorithm for Projective Clustering, section 5.1, second paragraph, second line.
Project clustering is a natural generalization of k-...
1
vote
0answers
72 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
136 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
3answers
463 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
125 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
283 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
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 ...
2
votes
0answers
87 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
214 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 ...
11
votes
1answer
304 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-...
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
224 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
111 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
63 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
1answer
88 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
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 ...
3
votes
1answer
91 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 ...
4
votes
0answers
78 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
507 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
317 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 ...
7
votes
1answer
172 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
102 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
125 views
Why are folded Reed Solomon Codes considered non linear?
This is for my understanding. What am I missing?
7
votes
1answer
242 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
110 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 ...
3
votes
0answers
83 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 $...
3
votes
0answers
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 ...
14
votes
1answer
656 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
494 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
755 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
237 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
231 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
80 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 ...
8
votes
2answers
575 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
991 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
votes
0answers
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 ...
4
votes
1answer
166 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
473 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 ...
6
votes
1answer
217 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
73 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 ...
