Questions tagged [0-1-matrices]
Questions involving results for the special case of matrices over the integers, reals, or complex numbers in which all coefficients are 0 or 1 (e.g. permutation matrices and adjacency matrices of graphs or digraphs).
8 questions
0
votes
0
answers
54
views
How can we tighten the bounds of the $\ell_1$-norm of $\mathbf{A}x$ where $\mathbf{A}\in\mathbb{Z}^{m\times p}$ and $x \in \{0,1\}^p$?
I am curious about the upper bound of $\|\mathbf{A}x\|_1$ where $\mathbf{A}\in\mathbb{Z}^{m\times p}$ and $x \in \{0,1\}^p$, for a specific $\mathbf{A}$ as defined below.
I know this is an NP-hard ...
0
votes
1
answer
118
views
Configurations of signs in a matrix under certain conditions
I have a combinatorial question which is out of my research area.
Given a $2^k\times 2^k$ matrix $A=[a_{i,j}]$ with entries in $\lbrace0,\pm1\rbrace$, where $k$ is a positive integer. Is it possible ...
- 619
0
votes
0
answers
49
views
Possible determinants of 01-matrices with at most three 1s in each row, column
As a function of $n$, what is the set of possible determinants of $n \times n$ matrices whose elements are 0s and 1s and have at most three 1s in each row and column?
I really enjoyed the problem ...
- 429
6
votes
0
answers
199
views
Zero-one pairings between sets of vectors
Let
$A\subseteq V$ and
$B\subseteq V^\star$
be spanning sets in
a finite-dimensional real vector space $V$ and
its dual $V^\star$.
Suppose that
$$
\langle b,a\rangle\in\lbrace0,1\rbrace
$$
for all
$a\...
- 809
1
vote
0
answers
42
views
Compute 01-vectors in the orbit of a given vector wrt a finitely-generated abelian subgroup of SL(n,ℤ)
Given a vector $v\in\mathbb Z^n$ and pairwise commutative matrices $M_1,\dotsc,M_k\in \operatorname{SL}(n,\mathbb Z)$, how to compute all 01-vectors in the orbit of $v$ with respect to multiplication ...
- 34.3k
5
votes
0
answers
184
views
Number of {0,1}-matrices with an even number of 1’s in each row vs in each column
I am working on an equation that would be solved if I show the following.
Let $k \geq l$, and consider the set of $\{0,1\}$-matrices of size $k \times l$ with exactly $i$ 1’s. Consider the subset $\...
- 891
3
votes
0
answers
86
views
An exponential integral over a closed convex polytope
For any $T\geq 2$, let us define the polyhedron $S$ given by
\begin{align*}
S:=\{\underline{t}:=(t_0,t_1,t_{2},t_{3},t_{4},t_{5},t_{6},t_{7})\in [0,+\infty)^{8}:A\underline{t}\leq (\log T)\textbf{1}\}
...
3
votes
2
answers
370
views
Bounds on singular values of invertible 0-1 matrices
I'm interested in considering digraphs from an algebraic perspective, which leads me to the following question.
Consider an invertible 0-1 matrix of shape $n \times n$.
What lower and upper bounds ...
- 1,414