All Questions
7 questions
1
vote
1
answer
187
views
A combinatorial matrix reconstruction problem II
For a positive integer $n$, let an $n$-shuffle be a multiset
$S=[(S_i,d_i)|i=1,\ldots,n]$ of pairs $(S_i,d_i)$, where each
$S_i$ is a multiset of $n$ numbers containing the number $d_i$.
A realization ...
- 3,873
1
vote
1
answer
209
views
Deciding if given number is a permanent of matrix
The permanent of an $n$-by- $n$ matrix $A=\left(a_{i j}\right)$ is defined as
$$
\operatorname{perm}(A)=\sum_{\sigma \in S_{n}} \prod_{i=1}^{n} a_{i, \sigma(i)}
$$
The sum here extends over all ...
2
votes
1
answer
140
views
Matrix completion problem with determinant condition?
Given two $\{0,1\}^{n\times n}$ matrices $L$ and $M$ and an integer $m$ is there a polynomial in $n$ algorithm to find a $\{-1,0,+1\}$ matrix $T$ such that $$\mathsf{det}(L+T\odot M)=m$$ where $\odot$ ...
- 13.9k
8
votes
3
answers
2k
views
Transforming a binary matrix into triangular form using permutation matrices
I am interested in the complexity of the following problem:
Given an $m\times n$ binary matrix $M$, can we permute its rows/columns to obtain a triangular matrix?
I am also interested in ...
- 1,271
5
votes
1
answer
523
views
Finding sparsest solution of a linear system
I want to find the solution with most zero-components for the following problem:
$Ax=b$ for $A\in \mathbb{R}^{k\times n}, b \in \mathbb{R}^{k},k<n$, where $x$ is real and has no additional ...
- 183
13
votes
0
answers
713
views
Regular languages of matrices and their generating functions
My question is somewhat related to this question.
Let us fix natural numbers $k$ and $C$. Let $A$ be an automaton whose alphabet consists of $k\times k$ matrices with integer coefficients of ...
- 3,897
1
vote
0
answers
576
views
Minimizing quadratic form over permutations
Let $Q$ be an $n \times n$ real symmetric matrix and $x$ an $n \times 1$ real vector. Consider the following minimization problem:
$\min_{\pi \in S_n} ~(\pi x)^{\rm T} Q (\pi x)$,
where $S_n$ ...
- 1,839