Questions tagged [linear-algebra]

Linear algebra deals with vector spaces and linear transformations.

Filter by
Sorted by
Tagged with
0
votes
0answers
370 views

norms of compressible and incompressible vector

Let $a$ be a vector in $R^m$, such that $\sum_{i=1}^ma_i=0$ I would like to bound $\sqrt{2m(2m-1)}\|a\|_{\infty}$ by $\sqrt{2m}\|a\|_2$ (or other way arround with the sharp constants), in the case ...
2
votes
1answer
110 views

Finding mapping between two spatial representations of the same objects

I have two matrices $U$ and $V$. $U$ is $n \times n$ and $V$ is $n \times m$. (Both are empirical results of an experiment.) I would like to find a linear transformation $A$, $m \times n$, such that $...
9
votes
2answers
557 views

Midpoint solutions to linear programs

There is a linear program for which I want not merely a solution but a solution that's as central as possible on the face of the polytope that assumes the minimal value. A priori, we expect the ...
18
votes
3answers
2k views

Determinant modulo m

What are the known efficient algorithms for computing a determinant of an integer matrix with coefficients in $\mathbb{Z}_m$, the ring of residues modulo $m$. The number $m$ may not be prime but ...
1
vote
1answer
2k views

What is the significance of abstract linear algebra in machine learning/computer vision research?

I am a computer science research student working in application of Machine Learning to solve Computer Vision problems. Since, lot of linear algebra(eigen-values, SVD etc.) comes up when reading ...
13
votes
1answer
499 views

Algorithmic Vector Problem

I have an algebraic problem related to vectors in the field GF(2). Let $v_1, v_2, \ldots, v_m$ be (0,1)-vectors of dimension $n$, and $m=n^{O(1)}$. Find a polynomial time algorithm that finds a (0,1)-...
14
votes
1answer
497 views

Log-space reduction from Parity-L to CNOT circuits?

Question. In their paper Improved simulation of stabilizer circuits, Aaronson and Gottesman claim that simulating a CNOT circuit is ⊕L-complete (under logspace reductions). It is clear that it ...
11
votes
2answers
291 views

On $n$ dimensional manifolds and lattices

EDIT (By Tara B): I'd still be interested in a reference to a proof of this, as I had to prove it myself for my own paper. I'm looking for the proof of Theorem 4 that appears in this paper: An ...
15
votes
1answer
1k views

Solving a linear diophantine equation approximately

Consider the following problem: Input: a hyperplane $H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\}$, given by a vector $\mathbf{a} \in \mathbb{Z}^n$ and $b \in \mathbb{Z}$ in ...
7
votes
1answer
268 views

determining if a matrix of linear forms represents a non-degenerate matrix

Let $k$ be a field with $p$ elements. Consider the following computational problem Input: a natural number $n$, $n^2$ linear forms $M_{ij}$, $i,j=1,\ldots n$ in $n^2$ variables $X_{11}, \ldots X_{...
7
votes
0answers
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 ...
16
votes
4answers
2k views

Definition of matrix-multiplication exponent $\omega$

Colloquially, the definition of the matrix-multiplication exponent $\omega$ is the smallest value for which there is a known $n^{\omega}$ matrix-multiplication algorithm. This is not acceptable as a ...
7
votes
1answer
340 views

Complexity to calculate a full set of eigenvectors over a finite field

Let a full rank $n\times n$ matrix ${\bf A}$ with elements over $\mathbb{GF}(2)$. What is the worst case complexity to calculate $n$ linearly independent (over $\mathbb{GF}(2)$) vectors, such that ...
19
votes
1answer
798 views

Is solving systems of equations modulo $k$ in $\mathsf{coMod}_k\mathsf L$ for $k$ composite?

I'm interested in the complexity of solving linear equations modulo k, for arbitrary k (and with a special interest in prime powers), specifically: Problem. For a given system of $m$ linear ...
10
votes
1answer
564 views

Can such a matrix exist?

During my work i came up with the following problem: I am trying to find an $n \times n$ $(0,1)$-matrix $M$, for any $n > 3$, with the following properties: The determinant of $M$ is even. For ...
11
votes
0answers
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 ...
13
votes
1answer
326 views

Cases of nearly linear time solvable linear systems

Let a square $n\times n$ real matrix ${\bf A}$ and two vectors ${\bf x}$ and ${\bf b}$ of length $n$, such that $${\bf A}{\bf x}={\bf b}.$$ Solving for ${\bf x}$ through standard Gaussian Elimination ...
7
votes
0answers
193 views

Are the minimal quantum and classical span programs the same?

A span program is a linear-algebraic way of specifying a boolean function introduced here which has found recent application in quantum query complexity. A span program for a function $f: \{0,1\}^n \...
10
votes
1answer
452 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 ...
7
votes
0answers
135 views

What's new in sparse eigensystems solution

As a part of other work I need to solve relatively large (~1E5x1E5) and sparse (~100 non-zero elements in each raw in few blocks) hermitian eigensystems. Usually only few eigenvalues+vectors are ...
19
votes
2answers
1k views

A data structure for minimum dot product queries

Consider $\mathbb{R}^n$ equipped with the standard dot product $\langle \cdot, \cdot \rangle$ and $m$ vectors there: $v_1, v_2, \ldots, v_m$. We want to build a data structure that allows queries of ...
3
votes
0answers
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 ...
5
votes
0answers
271 views

Hardness of finding eigenvalues?

Is there a setting in which finding eigenvalues/eigenvectors is computationally hard? Or at least, not known to be computationally easy? For example, how computationally hard or easy is it to find ...
10
votes
2answers
419 views

Restricting entries of unitary operators to real numbers and universal gate sets

In Bernstein and Vazirani's seminal paper "Quantum Complexity Theory", they show that a $d$-dimensional unitary transformation can be efficiently approximated by a product of what they call "near-...
10
votes
1answer
355 views

What is the largest gap between rank and approximate rank?

We know that the log of the rank of a 0-1 matrix is the lower bound of deterministic communication complexity, and the log of the approximate rank is the lower bound of randomized communication ...
18
votes
1answer
608 views

What is the most general structure on which matrix product verification can be done in $O(n^2)$ time?

In 1979, Freivalds showed that verifying matrix products over any field can be done in randomized $O(n^2)$ time. More formally, given three matrices A, B, and C, with entries from a field F, the ...
2
votes
2answers
386 views

LU factorization of a 0-1 matrix

I have a rather naive question on LU factorization which probably should be easy to answer. Say I have a matrix with entries only from $\{0,1\}$. When can we expect to get an LU factorization of such ...
14
votes
0answers
508 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 ...
15
votes
2answers
4k views

What is the fastest algorithm to compute rank of a rectangular matrix?

Given an $m \times n$ matrix (assuming $m \ge n$), what is the fastest algorithm to compute its rank and basis of the columns? I am aware it can be solved through linear matroid intersection, which ...
9
votes
2answers
260 views

Polynomial algorithms for UPB (Unextendable Product Bases)

Consider a Hilbert space $H = H_1 \otimes \dots \otimes H_n$. An Unextendable Product Basis (UPB) is a set of product vectors $\vert v_i \rangle = \vert v_i^1 \rangle \otimes \dots \otimes \vert v_i^n ...
9
votes
0answers
540 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 ...
59
votes
4answers
3k views

Evidence that matrix multiplication can be done in quadratic time?

It is widely conjectured that $\omega$, the optimal exponent for matrix multiplication, is in fact equal to 2. My question is simple: What reasons do we have for believing that $\omega = 2$? I'm ...
8
votes
1answer
289 views

Transitive closure of an affine relation

I am looking for work on computing the transitive closure of an affine relation in the following sense: Let $R(x_1,\dots,x_n,x'_1,\dots,x'_n)$ be the relation defined by a system of linear ...
79
votes
2answers
25k views

What is the actual time complexity of Gaussian elimination?

In an answer to an earlier question, I mentioned the common but false belief that “Gaussian” elimination runs in $O(n^3)$ time. While it is obvious that the algorithm uses $O(n^3)$ arithmetic ...
13
votes
1answer
3k views

Matrix multiplication in $O(n^2 \log n)$

I was searching about Matrix multiplication, So I first visit wiki matrix multiplication algorithms, In references I found a paper which claim that uses $O(n^2 log(n))$ algorithm , I'd going to read ...
9
votes
1answer
3k views

Complexity of Finding the Eigendecomposition of a *Symmetric* Matrix

This is a specialized version of a previous question: Complexity of Finding the Eigendecomposition of a Matrix . For NxN symmetric matrices, it is known that O(N^3) time suffices to compute the ...
5
votes
3answers
365 views

Calculating a fast matrix vector product between vector of reals and a 0-1 matrix

Given: some vector $R=(r_1...r_l)$ - real numbers, and a set of distinct vectors with $0$ or $1$ coordinates $$\begin{array}{c} V_1=(c_{1,1} ... c_{1,l}),\\ V_2=(c_{2,1} ... c_{2,l}),\\ .....\...
20
votes
3answers
1k views

Survey on algorithms/complexity of linear algebra

I am looking for a good survey on algorithms and complexity of linear algebra (operations like rank, inverse, eigenvalues, ... for Boolean, $\mathbb{F}_p$, and integers/rationals matrices) with ...
41
votes
6answers
14k views

Complexity of Finding the Eigendecomposition of a Matrix

My question is simple: What is the worst-case running time of the best known algorithm for computing an eigendecomposition of an $n \times n$ matrix? Does eigendecomposition reduce to matrix ...
18
votes
2answers
839 views

A Boolean function that is not constant on affine subspaces of large enough dimension

I'm interested in an explicit Boolean function $f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}$ with the following property: if $f$ is constant on some affine subspace of $\\{0,1\\}^n$, then the dimension ...
15
votes
1answer
736 views

Sparse Walsh-Hadamard Transform

The Walsh-Hadamard transform (WHT) is a generalization of the Fourier transform, and is an orthogonal transformation on a vector of real or complex numbers of dimension $d = 2^m$. The transform is ...

1 2 3
4