All Questions
Tagged with computer-science linear-algebra
23 questions
22
votes
9
answers
17k
views
Fast evaluation of polynomials
Hello everybody !
I was reading a book on geometry which taught me that one could compute the volume of a simplex through the determinant of a matrix, and I thought (I'm becoming a worse computer ...
- 1,654
15
votes
2
answers
3k
views
How to compute the rank of a matrix?
Okay, that's a misleading title. This is a somewhat subtler problem than undergraduate linear algebra, although I suspect there's still an easy answer. But I couldn't resist :D.
Here's the actual ...
- 12.6k
13
votes
0
answers
257
views
Is the set of power matrices decidable?
Let $\text{Mat}(n\times n,\mathbb{Z})$ denote the collection of integer $n\times n$ matrices. We say $M\in \text{Mat}(n\times n,\mathbb{Z})$ is a power matrix if there is an integer $k>1$ and a ...
- 48.9k
12
votes
1
answer
4k
views
How to check whether a positive integer can be written as linear combination of given others, where all coefficients are positive?
Let $n$, $k$ and $m_1, \dots, m_k$ be positive integers. Which is the most efficient
algorithm to find out whether there are positive integers $a_1, \dots, a_k$ such that
$n = \sum_{i=1}^k a_i m_i$?
...
- 241
8
votes
1
answer
585
views
Main problems on lattice-basis reduction algorithms (such as LLL)?
What are the main open problems on lattice-basis reduction algorithms (such as LLL)? I am looking for problems satisfying the following two conditions:
(a) their solution would likely be of some ...
- 20.2k
5
votes
9
answers
7k
views
Applications of basic linear algebra concepts to computer science? [closed]
I'm trying to explain linear algebra to some programmers with computer science backgrounds. They took a course on it long ago, but don't seem to remember much. They can follow basic formalism, but ...
- 4,164
5
votes
2
answers
680
views
Finding the solution to b = Ax that minimizes the Hamming weight (everything over the field F_2).
Is there an efficient algorithm for finding the solution $x$ of
$b = Ax$
that minimizes the Hamming weight of $x$, where
$A$ is a nxm-matrix over the field $\mathbb{F}_2$ ("integer matrix modulo 2")...
- 141
5
votes
0
answers
240
views
Complexity of approximating the size of the range of a matrix
Given an $m$ by $n$ matrix $M$ with $m \leq n$ and elements from $\{-1,1\}$, let us define:
$$S_M = |\{Mx : x \in \{-1,1\}^n\}.$$
It is NP-hard to compute $S_M$ exactly I believe by applying the ...
- 3,377
4
votes
1
answer
342
views
rank of an integer valued matrix
I make some numerical experiments, involving rank of integer valued matrices of the size about $14\times 24$. As the matrix is integer valued, theoretically there should be no room for errors. However ...
- 728
3
votes
1
answer
296
views
Question about the elementary divisors of a special matrix
I have the following question:
Is there a closed formula for the elementary divisors of the Matrix
$M=\lbrace (m_{ij})\rbrace_{i=1,...,n,\ j=1,...,k}$, where $m_{ij}$ is the greatest common ...
3
votes
1
answer
2k
views
Conditions that allow unique solutions for Linear Diophantine equations
(This posting became very long, so I should note that there are two alternative but nearly equivalent formulations of the same question being given. The first one asks for the optimal strategy for ...
3
votes
1
answer
98
views
Lattice basis reduction over rings of number fields
Can one use lattice basis reduction algorithms, such as LLL over (low-rank) module lattices over rings of number fields of degree greater than 1? Is there any work on lattice reductions over Euclidean ...
- 1,099
3
votes
0
answers
311
views
what is the largest gap between rank and approximate rank
$\epsilon$-approximation rank of a matrix $M$ is the minimum rank of a real matrix $A$ which differs from $M$ at most $\epsilon$ in each entry. Associating any function $f:X\times Y\rightarrow${1,-1} ...
- 363
3
votes
0
answers
328
views
Integer relation detection for Subset Sum or NPP?
Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic ...
- 513
2
votes
2
answers
169
views
Decidability of matrix problem in ${\mathbb Z}/p{\mathbb Z}$
Let $p$ be a prime number, $n$ be a positive integer, and let ${\mathbb Z}_p^{n\times n}$ denote the set of $n\times n$-matrices over ${\mathbb Z}/p{\mathbb Z}$.
Suppose we are given an integer $m>...
- 48.9k
2
votes
1
answer
102
views
Maximum number of $0$-$1$ vectors with a given rank
Let $k\ge2$. The maximum number of $0$-$1$ (column) vectors of length $2k-1$ which make a rank $k$ matrix with no zero row nor two identical rows is $2^{k-1}+1$. (The rank is over the rationals.)
I ...
- 33
2
votes
0
answers
99
views
Recovering a rank-one matrix from its eigendecomposition after randomized rounding [closed]
Let $A = xy^T$ be a rank-$1$ matrix, and suppose every entry of $A$ is in $[0,1]$. We can create a binary matrix $A_{\rm rounded}$ by setting
$$ [A_{\rm rounded}]_{ij} = \begin{cases} 1 & \mbox{ ...
- 121
1
vote
1
answer
210
views
Extracting integer multiplicative factors from the sum of certain sets of (finite-precision) real numbers?
Update based on Michael's answer (thanks again!) - Can the LLL or PSLQ algorithms provide a (knowably - i.e. not just incidental) unique solution for the set of integer multiplicative factors? Are ...
- 43
1
vote
1
answer
90
views
Probability of collision of sums of vectors multiplied by random matrix
Let $S$ and $T$ be sets of vectors from $\mathbb{R}^d$ such that $S$ and $T$ are at least different in one element.
Does there exist a random matrix $M \in \mathbb{R}^{d \times k}$, e.g., a gaussian ...
- 321
1
vote
0
answers
109
views
Problems Correction of "Algebra, Topology, Differential Calculus, and Optimization Theory For Computer Science and Machine Learning "' [closed]
Where I can find the problems correction of this book " Algebra, Topology, Differential Calculus, and Optimization Theory For Computer Science and Machine Learning "
- 11
1
vote
1
answer
82
views
Understanding statement about bounds of vector in the context of a RSDF ≤ₘ WOPT proof
I'm trying to follow the proof of Lemma 4 of "Strong NP-Hardness of the Quantum Separability Problem", by S. Gharibian, 2010 [1], which, roughly, states that there is a many-one reduction ...
- 11
0
votes
0
answers
104
views
Efficient Algorithm to Find Subset of Vectors Over $\mathbb{F}_q$ Living in Low Dimensional Subspace
Let $q$ be a fixed prime, $P, Q$ be polynomials with $\mathrm{deg}(Q) < \mathrm{deg}(P)$ and $h = O(\log n)$.
Let $S$ be a subset of $\mathbb{F}_q^n$ of size $P(n)$ such that there exists a subset ...
- 328
0
votes
1
answer
312
views
Deriving the fundamental equation (with regards to computer vision)
I'm having a hard time understanding how a few equations are being derived. So the fundamental equation is an equation that relates corresponding points in stereo images. Anyway, that's the basic ...
