Linear algebra deals with vector spaces and linear transformations.

learn more… | top users | synonyms

0
votes
0answers
28 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
105 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
votes
0answers
27 views

eigenvalue of the product of a circulant matrix and diagonal matrix

Suppose we have a circulant matrix (A) and a diagonal matrix (B). Both of the matrices are of order n * n. The elements in the diagonal matrix are all different. Is there an algorithm to compute the ...
1
vote
1answer
41 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
25 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
180 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
133 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
127 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
90 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
814 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
378 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
75 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
138 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
54 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
187 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
96 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
138 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
423 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
103 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
164 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
95 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
90 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
147 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
124 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
714 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
227 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
194 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
222 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
579 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
168 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
293 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
133 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
289 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
177 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
326 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
479 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
538 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
380 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
121 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
214 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
324 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.
23
votes
0answers
590 views

Complexity of matrix powering

Let $M$ be a square integer matrix, and let $n$ be a positive integer. I am interested in the complexity of the following decision problem: Is the top-right entry of $M^n$ positive? Note that the ...
10
votes
1answer
161 views

similar matrices

Given two $n \times n$ matrices $A$ and $B$, the problem of deciding if there exist a permutation matrix $P$ such that $B = P^{-1}AP$ is equivalent to GI(Graph ...
8
votes
0answers
111 views

Extension of Cheeger's inequality with distinguished vertices

The standard Cheeger's inequality for graph $G$ states that $\frac{1}{2}$ $\lambda$ < $\phi(G)$ < $\sqrt{2\lambda}$ where $\lambda$ is the second smallest eigenvalue of the normalized ...
9
votes
0answers
372 views

Sampling from Multivariate Gaussian with Graph Laplacian (inverse) Covariance

We know from e.g. Koutis-Miller-Peng (based on work of Spielman & Teng), that we can very quickly solve linear systems $A x = b$ for matrices $A$ that are the graph Laplacian matrix for some ...
1
vote
0answers
211 views

application for the Kchinchine inequality in Computer Science

The classical Kchinchine inequality states that for vector $a=(a_1, \ldots, a_{2m})\in R^{2m}$, for $p\geq 2$, and for independent Rademacher random variables $r_1, \ldots, r_{2m}$, one has $$ ...
-5
votes
1answer
236 views

Solving a system of linear inequations

Consider the following system of inequalities: $Ax=b$; $x\geq 0$; A is a $m\times n$ (non-square) and sparse matrix in which some part of entries are rational. a) How feasibility of this system can ...
12
votes
1answer
294 views

Two matrices related by a permutation $B = P A P^T$ - complexity

What is computational complexity of the following problem: given two complex $n\times n$ matrices $A$ and $B$ check if there is a permutation matrix $P$ such that: $$B = P A P^T.$$ If it helps, one ...
19
votes
2answers
616 views

Linearly independent Fourier coefficients

A basic property of vector spaces is that a vector space $V \subseteq \mathbb{F}_2^n$ of dimension $n-d$ can be characterized by $d$ linearly independent linear constraints - that is, there exist $d$ ...