Tagged Questions

Linear algebra deals with vector spaces and linear transformations.

learn more… | top users | synonyms

0
votes
0answers
53 views

k closest points that belong to a set

This is a question from theory community, but I came across this issue in a practical problem. So just have this in mind. I have a set of real vectors: $$ S = \lbrace v_1, \dots, v_n \rbrace $$ ...
3
votes
1answer
64 views

Approximation algorithms for min vector subset-sum over GF(2)

In this question vzn asked about the following problem, which I'll call Vector-Subset-Sum. Given a set of vectors $v_i$ over GF(2) and a target vector $y$, is there a subset of the $v_i$ summing ...
1
vote
0answers
30 views

NC algorithm for rank of skinny matrix

Suppose I want to find the rank of an $m \times n$ matrix $A$ over $GF(2)$, where $m \ll n$. The algorithms for rank in the literature seem to be focused on the case when $m = n$, giving a time ...
2
votes
0answers
68 views

efficient data structures for generalized tensor products

The usual tensor product of vectors is a matrix. There has been tons of research into efficiently storing and operating on matrices in computers. But we can generalize the tensor product quite a ...
0
votes
0answers
46 views

Minimum vector sets span spaces cover problem

Instance: a set of vectors $V=\{\mathbf{v}_1,\mathbf{v}_2,...,\mathbf{v}_n\}$ and $m$ vector sets $V_1,V_2,...,V_m$, each of which contains multiple vectors ($V_i$ may not be a subset of $V$). In our ...
5
votes
0answers
133 views

Extensions of Affine Dispersers

A function $f\colon\{0,1\}^n\to\{0,1\}$ is called an affine disperser for dimension $d$, if for every affine subspace $S\subseteq \{0,1\}^n$ of dimension at least $d$, $f$ is not constant on $S$. This ...
1
vote
0answers
106 views

Computing a sparse eigenvector

Given a matrix $A$ with distinct eigenvalues, can I find a sparsest eigenvector of it in polynomial time? It is tempting to say that one can simply compute the eigenvectors and pick the sparsest ...
0
votes
0answers
92 views

Fastest Algorithms for Determining the Nullity of a Matrix

How exactly does one go about determining the Nullity of a Matrix quicker than simply running Gaussian Elimination on the matrix itself? To be perfectly honest I can't think of a method that doesn't ...
3
votes
0answers
93 views

Algorithm (parallel and serial) for Gram-Schmidt

Suppose we are given $m$ vectors $v_1, \dots, v_m$ in $n$-dimensional space $\mathbf R^n$ (or perhaps they are specified up to $b$ bits of precision). I would like to find an orthonormal basis for the ...
0
votes
0answers
37 views

Sparse matrix-vector multiplication materials needed

I've been assigned a project at school, the theme is the influence on cache memory when doing sparse matrix-vector multiplications. I've been searching for materials for quite some time but all I can ...
7
votes
0answers
157 views

Gaussian elimination for inverting matrices modulo prime power

Can I use Gaussian elimination to compute matrix inverse over the ring $\mathbb{Z}_{p^k}$ (ring of residues modulo $p^k$) where $p$ is prime and $k$ is an integer greater than $1$? Such matrix is ...
1
vote
1answer
48 views

Subspace-evasive set performance in the random case

A subspace evasive set is defined as a large subset of a vector space which has small intersection with any $k$ dimensional affine space. That is, it "evades" all affine subspaces of small enough ...
1
vote
0answers
26 views

Decoding of Gabidulin codes

Consider the space of matrices in $\mathbb{F}_q^{n \times m}$ where $\mathbb{F}_q$ is the finite field with $q$ elements. We can define a metric on this space, given by $d(A,B) := rank(A-B)$, called ...
3
votes
1answer
197 views

A matrix rank problem over finite fields: Is that a known problem?

The following problem is simple to state, but seems quite complicated to solve to me. Any hint or reference to related work is appreciated. Let $A \odot B$ denote elementwise multiplication of ...
3
votes
0answers
139 views

An interesting construction of a Tits building?

The notion of Tits building was introduced by Jacques Tits to study certain questions in group theory. The wikipedia entry gives a way to construct a Tits building from a vector space, but I would be ...
4
votes
0answers
163 views

Extensions of Sylvester's inertia law?

Sylvester's inertia law deals with the signatures of quadratic forms. I was thinking that it may be possible to extend this to multilinear forms; here is a first attempt. Let $M$ be a $k$-linear form ...
2
votes
1answer
144 views

Parallel (NC) replacements for Gaussian elimination?

Suppose one has an matrix $A$ with $c$ columns and $r$ rows with entries in the binary field $GF(2)$. One wants to determine its rank, and a basis for its null-space. These can be computed ...
3
votes
1answer
91 views

compleixty of rational checking of eigenvalues

Given a matrix $A$ with rational entries, how to check whether all the eigenvalues of $A$ are rational? What's the complexity of this problem? It seems that this can be done in polynomial time, but ...
24
votes
3answers
904 views

Decide whether a matrix's kernel contains any non-zero vector all of whose entries are -1, 0, or 1

Given an $m$ by $n$ binary matrix $M$ (entries are $0$ or $1$), the problem is to determine if there exists two binary vectors $v_1 \ne v_2$ such that $Mv_1 = Mv_2$ (all operations performed over ...
20
votes
1answer
384 views

Is there a polynomial time algorithm to determine if the span of a set of matrices contains a permutation matrix?

Precisely what the title says, I'm looking to find a polynomial time algorithm that given some set of matrices, will find if their span contains a permutation matrix. If any one knows if this ...
1
vote
0answers
82 views

Constructing a digraph from its spectrum

This is related to the following question which has already been explored: Reverse Graph Spectra Problem? So it seems as if given a sequence of real numbers, it is not always possible to generate a ...
10
votes
0answers
142 views

Number of graphs with prescribed spectrum

I have a question relevant to the number of graphs with prescribed spectral ratio. Let $A$ be the adjacency matrix of a graph on $n$ vertices. Let $\lambda_i$ be its $i$-th largest (signed) ...
3
votes
0answers
57 views

Finding the closest subspace to a collection of subspaces

Suppose we have a collection of linear subspaces $\mathbb{C}$ lying in $\mathbb{R}^d$, such that each $c \in \mathbb{C}$ is of dimension at most $k \leq d$ for a given fixed $k$ and $|\mathbb{C}| = ...
0
votes
1answer
208 views

Has anyone mixed linear algebra with formal language theory in this way?

Let $G$ be the grammar: $$ S \rightarrow aAb \\ A \rightarrow aA + a + \epsilon $$ where $\epsilon$ is the empty string, $a,b$ are terminals and $S,A$ non-terminals with $S$ the start symbol. ...
3
votes
0answers
106 views

Spectral Graph Theory and Matroid Theory

I have just started grad school this year and I have been into Spectral Graph Theory for some time now. Recently I got introduced to Matroid Theory and although I know the field has been around for ...
1
vote
0answers
152 views

Time complexity of clustering based on random walk

What is the time complexity of the following algorithm (from this paper suggested by Zhou) to partition directed graph? Can I use the complexity of eigen vector computation for this purpose? The ...
13
votes
1answer
426 views

What's the complexity to check whether a matrix is Diagonalizable?

Given an $n\times n$ matrix $A$ with rational entries. What's the complexity to check $A$ is diagonalizable? I suspect that this can be done in P, but I do not know any reference. However, a more ...
1
vote
0answers
122 views

Running time of Jacobi vs Golub-Kahan for SVD

For an $m \times n$ matrix, what is the running time for computing the Singular Value Decomposition (SVD for short) via Jacobi's method, and Golub-Kahan? The source I read mentions that Jacobi's ...
4
votes
1answer
173 views

state-of-the-art bit complexity of the determinant

I'm trying to understand the full bit-complexity of computing the determinant of an $n\times n$ integer matrix, with each entry represented by $M$ bits. I would like to know what is the ...
-3
votes
1answer
111 views

the product of a matrix and a permutation matrix [closed]

Can a permutation matrix (P) be used to change the rank of another matrix (M)? Is there any literature to this effect, or to the contrary? I've tried a few small examples and the resulting matrix ...
2
votes
0answers
109 views

normalized tensor rank

Is there such a thing as a "normalized tensor rank" for non-square tensors (i.e. a tensor with different sizes along each mode)? For example: If a 3rd order tensor (dimensions = 60 x 120 x 30) has ...
11
votes
0answers
150 views

the largest element of a matrix product

Given two matrices, I'm interested in finding the largest element of their product. I wonder if it's possible to do it significantly faster than the matrix multiplication the solution seems to ...
0
votes
1answer
133 views

Various conjectures which is similar to Log Rank conjecture

Log rank conjecture is one of the most famous open problems in the area of communication compleixty. Lets consider the two party cdommunication complexity. Alice and Bob have $n$ bit strings $a,b$ , ...
17
votes
4answers
729 views

Checking if all products of a set of matrices eventually equal zero

I am interested in the following problem: given integer matrices $A_1,A_2, \ldots, A_k$ decide if every infinite product of these matrices eventually equals the zero matrix. This means exactly what ...
7
votes
0answers
251 views

An algorithm to compute the number of paths of length at most k

So I had to answer the following question: Given a graph $G = (V, E)$, and two vertices $v_i, v_j$, compute the number of walks between $v_i$ and $v_j$ of length at most $k$. $G$ is not too large, ...
1
vote
1answer
237 views

What is the advantage of a transformation matrix in perspective projection?

I was messing around with perspective projection. And it got me wondering whether using a perspective transformation matrix is the most efficient way. Because I also came up with another method which ...
10
votes
1answer
240 views

Why does the log-rank conjecture use rank over the reals?

In communication complexity, the log-rank conjecture states that $$cc(M) = (\log rk(M))^{O(1)}$$ Where $cc(M)$ is the communication complexity of $M(x,y)$ and $rk(M)$ is the rank of $M$ (as a ...
18
votes
4answers
584 views

How to obtain the unknown values $a_i,b_j$ given an unordered list of $a_i-b_j\mod N$?

Can anyone help me with the following problem? I want to find some values $a_i,b_j$ (mod $N$) where $i=1,2,…,K, j=1,2,…,K $ (for example $K=6$), given a list of $K^2$ values that correspond to the ...
8
votes
0answers
174 views

Counting small terms in a determinant calculation over polynomials (counting spanning trees by weight)

I have a $n\times n$ matrix $A$. It's terms are $a_{ij}=-x^{w_{ij}}$ if $i\neq j$ and $a_{ii}=\sum_{j=0}^{n+1} x^{w_{ij}}$ on the diagonal. The matrix is symmetric as $w_{ij}=w_{ji}$. Numbers $w_{ij}$ ...
16
votes
2answers
315 views

Bigger picture behind the choice of matrices in the Strassen algorithm

In the Strassen algorithm, to compute the product of two matrices $\mathbf{A}$ and $\mathbf{B}$, the matrices $\mathbf{A}$ and $\mathbf{B}$ are divided into $2 \times 2$ block matrices and the ...
12
votes
0answers
137 views

Complexity to compute the eigenvalue signs of the adjacency matrix

Let $A$ be the $n\times n$ adjacency matrix of a (non-bipartite) graph. Assume that we are given the amplitudes of its eigenvalues, i.e., $|\lambda_1|=a_1,\ldots, |\lambda_n|=a_n$, and we would like ...
7
votes
1answer
323 views

How do database aggregations form a monoid?

On cs.stackexchange I asked about the algebird scala library on github, speculating on why they might need an abstract algebra package. The github page has some clues: Implementations of Monoids ...
3
votes
1answer
188 views

What is this matrix column-selection problem, and how hard is it to approximate?

I ran across the following simple-to-state problem involving selection of a subset of columns simultaneously for a number of matrices. I suspect it might be well known, though I can't seem to place ...
2
votes
1answer
343 views

All Pairs Shortest Path - Directed graph with integer weights

I don't understand how Distance Product works (or Min Plus Product). If we replace each argument in $A$ from $a_{i,j}$ to $x^{a_{i,j}}$ and each argument in $B$ from $b_{i,j}$ to $x^{b_{i,j}}$ and ...
15
votes
2answers
489 views

What is the space complexity of calculating Eigenvalues?

I am looking for a survey paper or a book covering results about the space complexity of common linear algebra operations such as matrix rank, eigenvalues calculation, etc. I stress the "space ...
2
votes
2answers
670 views

Minimizing the maximum dot product among k unit vectors in an n-dimensional space

Suppose, we are given a set of $k$ unit vectors $v_1,\ldots,v_k$ in $\mathbb{R}^n$. Consider all possible dot products among distinct vectors $v_i \cdot v_j$, where $i \ne j$. Let, $$\alpha = \max_{1 ...
5
votes
0answers
443 views

What is computational complexity of calculating the Variance-Covariance Matrix?

I am using a calculation of the Variance-Covariance matrix in a program I wrote (for Principal Component Analysis), and am wondering what the complexity of it is. While obviously the Eigenvector ...
1
vote
0answers
125 views

Trace minimization with an orthogonality constraint

For positive semi-definite matrices $A,B$, how can I find an $X$ that minimizes $\text{Trace}(AX^TBX$) under the constraint: that $X$ is orthogonal. All the matrices have real entries and $A,B$ are ...
4
votes
0answers
246 views

What about apply maxplus algebra for all-pairs shortest paths?

I didn't find deep informations on Wikipedia about all-pairs shortest path, in particular I do not know what is the best algorithm to solve this problem beyond Floyd-Warshall's one, then I do not know ...
10
votes
1answer
330 views

What is the asymptotically fastest known algorithm for computing the nullspace of a matrix?

I know Gaussian Elimination takes $O(n^3)$ arithmetic operations, but I'm unsure if any better algorithms are known.