# Questions tagged [linear-algebra]

Linear algebra deals with vector spaces and linear transformations.

227 questions
Filter by
Sorted by
Tagged with
1 vote
85 views

125 views

### Completing a matrix (over the reals) to be singular

Consider the following problem: you are given a matrix (say, with rational entries) some of whose entries are actually left blank; can these blanks be filled in with real numbers so that the resulting ...
243 views

### Complexity of eigenvalue problem

Many matrix diagonalization algorithms have time complexity $\mathcal{O}(n^3)$ where $n$ is the number of columns/raws (consider only square matrices). What is the best time lower bound it is known? ...
673 views

### the confusion about 'with high probability (w.h.p.)'

w.h.p. can often be seen in the analysis of randomized algorithms. It's definition can be seen here https://en.wikipedia.org/wiki/With_high_probability. However my confusion is that: Assuming we ...
317 views

### Vertices of a polytope

Consider the polytope $P=\{(x_1,x_2,...,x_n)\in \mathbb{R}^n| \sum_{i=1}^n x_i=1; 0\leq a_i\leq x_i\leq b_i, i=1,...,n\}$ where $a_i$ and $b_i$ are constant lower and upper bounds for $x_i$. Is it ...
88 views

### Inverting Matrix in Prony's Algorithm

I'm reading Ankur Moitra's excellent lectures notes at http://people.csail.mit.edu/moitra/docs/bookex.pdf . In Chapter4, the notes claim that a certain circulant matrix of fourier coefficients is ...
237 views

### What is the space complexity of computing the eigenvectors of a matrix?

By the answer to this question, computing the eigenvalues of a matrix to within $2^{-n}$ precision can be done in polylogarithmic space. Is it also possible to compute the eigenvectors of a matrix to ...
1 vote
130 views

### Has there been work on formal Semantics for linear algebra?

Could I get some references on formal semantics for a calculus on linear algebra that helps you study matrix or tensor based programming languages? I am looking for anything that encompasses linear or ...
108 views

### Rigid families of $\{0,1\}$ matrices

We know that there are many families of matrices over $\Bbb F_q$, $\Bbb R$ etc are rigid. See http://mahdi.cheraghchi.info/talks/rigidity_talk.pdf Do we know there are many families of rigid REAL ...
274 views

172 views

### Finding the minimum number of coordinates to change to get a vector inside a subspace

Let $\mathbb F$ be a field (ex. a finite field, or the reals), $A$ a $m\times n$ matrix over $\mathbb F$, and $x\in \mathbb F^n$ a vector. I'm interested in finding the smallest number of coordinates ...
1 vote
87 views

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$$ $... 4 votes 1 answer 427 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 to ... 1 vote 0 answers 62 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 ... 3 votes 0 answers 252 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 bit.... 9 votes 0 answers 337 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 0 answers 118 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 ... 3 votes 0 answers 179 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 ... 7 votes 0 answers 460 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 ... 2 votes 1 answer 118 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 0 answers 45 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 ... 4 votes 1 answer 872 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 0 answers 197 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 0 answers 171 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 ... 4 votes 1 answer 474 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 easily ... 3 votes 1 answer 118 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 ... 26 votes 3 answers 1k 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$\... 879 views

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

I would like to find a polynomial time algorithm that determines if the span of a given set of matrices contains a permutation matrix. If any one knows if this problem is of a different complexity ...
1 vote
147 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 0-...
169 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) eigenvalue....
102 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}| = n$....
841 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. ...
370 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
536 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 ...
583 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 ...
278 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 ...
447 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 state-of-the-...
309 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)...
266 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 ...
644 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 ...
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$ , ...