Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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 ...
Dmitri Scheglov's user avatar
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 "
zdo0x0's user avatar
  • 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 ...
MikeEVMM's user avatar
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 ...
cha21's user avatar
  • 328
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 ...
Ebrahim's user avatar
  • 33
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 ...
Kim's user avatar
  • 4,164
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 ...
Dominic van der Zypen's user avatar
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{ ...
morgan's user avatar
  • 121
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 ...
Christopher's user avatar
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 ...
terett's user avatar
  • 1,099
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>...
Dominic van der Zypen's user avatar
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 ...
Simd's user avatar
  • 3,377
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$? ...
kyrpav's user avatar
  • 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 ...
H A Helfgott's user avatar
  • 20.2k
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 ...
Monkey D Ruffy's user avatar
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 ...
Jared Joke's user avatar
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 ...
Nathann Cohen's user avatar
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} ...
Penghui Yao's user avatar
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")...
David's user avatar
  • 141
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 ...
dorkusmonkey's user avatar
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 ...
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 ...
Richard's user avatar
  • 43
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 ...
Harrison Brown's user avatar