Questions tagged [linear-algebra]
Linear algebra deals with vector spaces and linear transformations.
227
questions
1
vote
0
answers
85
views
Compute basis of vertex set of polytope
I am wondering whether there is an efficient algorithm to compute the basis of the set of vertices of a polytope.
Formally,
INPUT: a polytope
$$\Xi=\{(\vec{a}_1\vec{x}+\vec{b}_1, \cdots, \vec{a}_m\...
- 89
14
votes
2
answers
1k
views
Checking equivalence of two polytopes
Consider a vector of variables $\vec{x}$, and a set of linear constraints specified by $A\vec{x}\leq b$.
Furthermore, consider two polytopes
$$\begin{align*}
P_1&=\{(f_1(\vec{x}), \cdots, f_m(\...
- 1,345
5
votes
0
answers
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 ...
- 51
3
votes
0
answers
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?
...
- 531
2
votes
0
answers
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 ...
- 179
-1
votes
1
answer
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 ...
- 253
0
votes
0
answers
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 ...
6
votes
0
answers
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 ...
- 161
1
vote
0
answers
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 ...
- 119
4
votes
0
answers
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 ...
- 12.8k
-1
votes
1
answer
274
views
convertion into integer linear program for Ising spin state problem [closed]
I am trying to model the Ising spin state problem into Integer linear program and find the optimal ground state using lp_solve. (This is just a miniature version of Ising state problem)
$$
maximise: \...
- 101
3
votes
1
answer
521
views
Rate of convergence for the Perron–Frobenius theorem
The Perron–Frobenius Theorem states the following.
Let $A = (a_{ij})$ be an $n \times n$ irreducible, non-negative matrix ($a_{ij} \geq 0, \forall i,j: 1\leq i,j \leq n$). Then the following ...
- 1,591
1
vote
0
answers
108
views
Complexity of Approximating Vandermonde Determinant
Given an $n\times n$ Vandermonde integer matrix with structured integers (such as arithmetic or geometric progression).
Is complexity of approximately computing Vandermonde determinant upto ...
- 12.8k
1
vote
0
answers
69
views
Matrix-convexity of inverse of the cofactor matrix [closed]
Consider the matrix-valued function $f(A) = \frac{A}{\det(A)}$ on the set of $3\times 3$ positive-definite matrices. Is this function matrix-convex ? (i.e., Is $tf(A) + (1-t)f(B) - f(tA+(1-t)B)$ ...
- 21
0
votes
0
answers
123
views
Is there a diagonal matrix D such that DMD is SDD, where M is SPD matrix
Let $M$ be symmetric and positive definite matrix (SPD). It is known [1] that
if $M$ is SPD and
in addition satisfies $M_{ij}\leq 0$, for $i\neq j$ (called M-matrix)
then there is a positive ...
- 1
5
votes
0
answers
159
views
Reconstruction of sparse vectors from random matrices
In the paper [A], the following linear algebra result (Lemma 5 in [A]) is stated as being well known. Note that a vector is $s$-sparse if it contains at most $s$ non-zero entries.
Lemma: Let $1 \...
5
votes
0
answers
131
views
Tools to bound the singular values of a finite sum of random matrices from below?
Matrix Chernoff bounds (see also this arXiv paper) are usually used to give upper bounds on the largest eigenvalue of a finite sum of random matrices. Sometimes it can also be used to give a lower ...
- 179
4
votes
2
answers
321
views
Is there a polynomial time algorithm for creating a set of vectors in general position?
It seems to be possible to create a set of vectors in $\mathbb{R}^n$ such that any subset of $n$ vectors forms a basis.
For example, in $\mathbb{R}^3$, here is such a set with 21 vectors:
$$
\left\{
...
- 155
4
votes
1
answer
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 ...
- 638
1
vote
0
answers
87
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
$$
$...
- 749
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,318
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,488
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....
- 1,063
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 ...
- 2,247
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 ...
- 11
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 ...
- 3,488
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 ...
- 71
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 ...
- 383
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 ...
- 383
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 ...
- 463
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 ...
- 1,292
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 ...
- 1,292
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,488
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 ...
- 1,345
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 $\...
user17100
30
votes
2
answers
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 ...
- 483
1
vote
0
answers
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-...
- 383
10
votes
0
answers
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....
- 1,346
3
votes
0
answers
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$....
- 729
6
votes
2
answers
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. ...
- 213
7
votes
0
answers
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
0
answers
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 ...
- 11
13
votes
1
answer
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 ...
- 133
2
votes
0
answers
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 ...
- 121
4
votes
1
answer
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-...
- 1,224
-3
votes
1
answer
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)...
- 17
2
votes
0
answers
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 ...
- 17
3
votes
2
answers
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 ...
- 101
12
votes
0
answers
267
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?...
- 231
0
votes
1
answer
262
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$ , ...
- 549