Questions tagged [linear-algebra]

Linear algebra deals with vector spaces and linear transformations.

180 questions
262 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 (M2)...
239 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 ...
556 views

Matrix multiplication algorithms for research

I am implementing a matrix library for use in my research. This should support 2D matrices of size 100x100 (or more perhaps later on). I am a little confused about the algorithm I should be using for ...
192 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 require?...
215 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$ , ...
848 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 ...
323 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, ...
938 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 ...
467 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 matrix)...
634 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 ...
188 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}$ ...
428 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 ...
178 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 ...
599 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 ...
254 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 it....
362 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 ...
704 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 ...
2k views

309 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 ...
337 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 ...
840 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$ ...
5k views

The computational complexity of matrix multiplication

I am looking for information about the computational complexity of matrix multiplication of rectangular matrices. Wikipedia states that the complexity of multiplying $A \in \mathbb{R}^{m \times n}$ by ...
231 views

Boolean error correcting code over $\mathbb{F}_q$

Is there any known construction of a linear error correcting code $\mathsf{ECC}:\mathbb{F}_q^n \to \mathbb{F}_q^m$ (with reasonable parameters), such that when given a Boolean vector $v\in \{0,1\}^n$, ...
80 views

Efficiently Detecting “edges” in the time frequency plane

Given a signal $y(t)\in\mathbb{R}$ I wish to detect edge patterns. $s(f,t)$ is a time-frequency decomposition of $y(t)$ in some window $(t-n,t+n)$ so that $f$ loosely corresponds to a local frequency....
381 views

179 views

513 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 ...
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 ...
1k 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 ...
475 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)-...
445 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 ...
265 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 ...
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 ...
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_{...