All Questions
Tagged with linear-algebra co.combinatorics
513 questions
8
votes
1
answer
2k
views
Complexity of finding a 0-1 vector in a subspace or showing that there is none
This question, is a slightly different disguise (see below), came up in discussions of this question about equitable partitions
A $0,1$ vector in $\mathbb{Z}^n$ is any vector with all entries $0$ and ...
- 30.1k
52
votes
2
answers
3k
views
vector balancing problem
I believe the solution posted to the arXiv on June 17 by Marcus, Spielman, and Srivastava is correct.
This problem may be hard, so I don't expect an off-the-cuff solution. But can anyone suggest ...
- 42.8k
15
votes
3
answers
737
views
Finding lots of discrete vectors in fairly general position
How many vectors can there be in $\mathbb{F}_2^{2n}$ such that no $n$ of them form a linearly dependent set? The bounds I have so far are embarrassingly far apart, though that probably means I should ...
- 29k
1
vote
0
answers
229
views
Counting equivalence classes in the transitive closure of two equivalence relations
Let $X$ be a finite set, and let $P_i$ and $Q_j$ be two partitions of $X$:
$$\bigsqcup_i P_i = \bigsqcup_j Q_j = X.$$
The finest partition which is nevertheless coarser than both $P$ and $Q$ is ...
- 5,898
2
votes
1
answer
137
views
Design constraint systems over the reals
This question is inspired by the discussion at this problem.
Suppose I have a design consisting of a finite point set $U$ of size $|U|=m_{\emptyset}$ and a family of $n$ subsets (sometimes called ...
- 30.1k
1
vote
2
answers
198
views
Finding a vector in the subspace
Given a $d$ dimensional vector $\bar{x} = [x_0,...,x_d]^t$,
how do I minimize $||\bar{x}-\bar{y}||_p$ such that $A\bar{y}=0$, for $p= 0$
i.e.,Minimize $L_0$ norm.
I also have the constraints that $...
- 13
6
votes
1
answer
643
views
q-analog of the matrix exponential
I am a fan of the Matrix exponential $\exp(X)$, defined for any complex matrix $X$ by
\begin{equation*}
\exp(X) := \sum_{k \ge 0} \frac{X^k}{k!}.
\end{equation*}
I have a fleeting acquaintance with ...
- 28.6k
10
votes
4
answers
4k
views
Sum of Gaussian binomial coefficients.
We all know that $\sum_{i=0}^{n}{n \choose i}=2^{n}$. Is there a similar result regarding the q-binomial coefficients? (a.k.a Gaussian binomial coefficients) - $\sum_{i=0}^{n}{n \choose i}_{q}=?$
- 119
1
vote
0
answers
165
views
Affine space partition of a general set
Olof Heden, in his work "A survey of the different types of vector space
partitions", discusses various results regarding the following qustion - given a vector space $V$ over a finite field, how can ...
- 119
1
vote
1
answer
254
views
references for families of conditionaly negative definite matrices
We say that a matrix $A\in M_n(\mathbb{C})$ is a conditionaly negative definite matrix if it is hermitian and if for all complex numbers $c_1,\ldots,c_n$ such that $c_1+\cdots +c_n=0$ we have
$$
\sum_{...
- 1,222
3
votes
3
answers
310
views
measuring $n\ 2$-planes in $\mathbb{R}^{2n}$
Given $n$ vectors $v_1, \ldots, v_n$ in $\mathbb{R}^n$ of course we all know at least one measure for their relative configuration: $|v_1 \wedge\ldots \wedge v_n|$. Now suppose one were given $n$ ...
- 2,274
4
votes
0
answers
189
views
Slices of Simplices that are Simplices, Reference?
I am trying to find a reference for the following fact. It is elementary and not hard to prove, but I haven't been able to find the question treated anywhere.
Let $A$ be an $l\times n$ matrix with ...
- 41
8
votes
3
answers
510
views
Equitable Allocation of Individuals to Positions
I'm not a mathematician but I working on a problem that feels like it an example of a more general kind of problem and I'm hoping that someone might be able to point me in the right direction.
The ...
- 317
8
votes
0
answers
694
views
Path connected set of matrices?
Consider the collection of $n$ by $n$ matrices
$$S=\{ A: A_{ij}\le0,\quad (-1)^{c_i}\det A(P_i;Q_i)<0 \quad \text{for} \quad i=1,\ldots, k\}$$
where $c_i\in \{0,1\}$, $P_i$ and $Q_i$ are disjoint ...
- 1,533
3
votes
0
answers
527
views
3-SAT and a matrix of linear forms representing a non-degenerate matrix
This is a follow-up to the previous question on the same topic. Thanks to Emil Jeřábek I can now ask a more specific question.
As before, let $k$ be a field with $p$ elements. Consider the ...
- 3,897
4
votes
1
answer
842
views
determining if a matrix of linear forms represents a non-degenerate matrix
Let $k$ be a field with $p$ elements. Consider the following computational problem
Input: a natural number $n$, $n^2$ linear forms $M_{ij}$, $i,j=1,\ldots n$ in $n^2$ variables $X_{11}, \ldots X_{...
- 3,897
3
votes
0
answers
390
views
Approximate action of unitary matrix with permutation matrix
Given a unitary matrix Q and a symmetric matrix B, I am trying to find a permutation matrix P such that
$ || QBQ^{T} - PBP^{T} ||_{F} $
is minimized.
The straightforward method of minimizing $ ...
6
votes
6
answers
2k
views
How many 0, 1 solutions would this system of underdetermined linear equations have?
The problem:
I have a system of N linear equations, with K unknowns; and K > N.
Although the equations are over $\mathbb Z$, the unknowns can only take the values 0 or 1.
Here's an example with N=11 ...
- 163
4
votes
1
answer
491
views
Generalization of the "double cap conjecture" to a vector space with complex field
The conjecture that I proposed in
Maximal set on hypersphere that does not contain pairs of orthogonal vectors
is in fact known as the "double cap conjecture", as noted by Guillaume Aubrun.
See for ...
- 1,207
3
votes
0
answers
212
views
Unique structures in a class of connected directed hypergraphs
Edit: The problem has been slightly revised, as I discovered that one of the questions I asked has an answer in the negative.
I'm working in a setting involving constraints on a system described by a ...
- 1,444
5
votes
1
answer
752
views
Convex Analytic or linear algebraic proof that a certain psd matrix is a sum of rank 1 psd matrices
Can you prove the following using techniques from convex analysis or linear algebra? I was originally seeking an elementary proof, but I think it is better to broaden the scope for this bounty ...
user2529
6
votes
1
answer
448
views
Counting the (additive) decompositions of a quadratic, symmetric, empty-diagonal and constant-line matrix into permutation matrices
Dear community,
I have the following combinatorial question which I will explain in short first and then with some more detail. At the end you will find a very simple example.
Short version
Le $A \...
- 199
3
votes
3
answers
3k
views
Laplacian spectrum for product graphs
Let $G$ and $H$ be simple graphs.
I am interested in the Laplacian spectrum for various products of $G$ and $H$ namely the cartesian product, tensor product, lexicographical product and strong product ...
- 3,463
2
votes
1
answer
200
views
Planar Graphs and Skew Binary Spaces
Let $G$ be a planar triangulation on $3m$ edges and $m+2$ vertices. Let $A$ be the binary matrix obtained from the incidence matrix of $G$ by deleting a row (equivalently we require the rows of $A$ to ...
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
32
votes
3
answers
3k
views
How much linear algebra can be done with graphs?
Let G be a finite directed acyclic graph, with sources $A=\{a_1,\ldots,a_n\}$ and sinks $B=\{b_1,\ldots,b_n\}$, with edge weights $w_{ij}$. The weight of a directed path P is the product of weights of ...
- 22.1k
5
votes
4
answers
2k
views
Determining a recurrence relation
I would like to solve the general problem of determining a linear recurrence relation that fits a given integer sequence of length $n$, or stating that none exists (with fewer than $n/2-k$ ...
- 9,114
0
votes
1
answer
340
views
[Matrices over Z] - An algorithm for calculating the diagonal with elementary operations
Dear mathoverflow,
Let
$
\left(
\begin{array}{cc}
a & b \newline
c & d
\end{array}
\right)
$
be a matrix with $a, b, c, d \in \mathbb{Z}$, $\gcd(a,b,c,d) = 1$ and $ad - bc = \pm N$, with $N &...
- 11
6
votes
2
answers
520
views
Upper bounds on the permanent of dense 0-1 matrix
I am looking for some result useful in deriving following (conjecture?):
Let $A$ be an $n\times n$ matrix with $0-1$ entries.
Suppose, that exactly $k\leqslant n$ entries are equal to $0$.
Then $\...
- 696
8
votes
1
answer
646
views
Projecting the unit cube onto a (very special) subspace
Let $n>1$ be an integer, and $a>1$ a real number. Consider the subspace $L<R^{2^n}$ generated by the $n$ possible tensor products of the $n-1$ copies of the vector $(1,a)$ and one copy of $(a,...
- 23k
28
votes
4
answers
2k
views
Matrices: characterizing pairs $(AB, BA)$
Let $A$ be an $m\times n$-matrix and $B$ an $n \times m$-matrix over the same field. Consider the matrices $C=AB$ and $D=BA$. It is probably well known (and not difficult to show) that the only ...
- 6,919
13
votes
7
answers
4k
views
Status of the Hadamard Circulant conjecture
The following feels like a community wiki question, so I do it here:
Recently we have heard of a new proof of the Circulant Hadamard conjecture of Ryser
(a long standing difficult conjecture):
...
12
votes
3
answers
2k
views
Representability of matroids over $\mathbb R$
Let $M$ be a matroid, for example viewed as being given by a finite set $X$ and a rank function $d : P(X) \to {\mathbb N}$ such that
1) $d(\varnothing)=0$, $d(\lbrace x \rbrace)=1$, for all $x \in X$,...
- 25.5k
16
votes
4
answers
3k
views
How many minors I need to check to conclude all minors will vanish ?
Given a $m \times n$ matrix $n>m$, I was trying to check if all its $m \times m$ minor vanish.
I remember hearing that one really does not need to check all possible minors in order to conclude ...
- 1,795
11
votes
2
answers
1k
views
An algorithm to find non-trivial linear dependencies
This question is inspired by another MO question about special stratifications of equivariant Grassmannians, that turned out to be a problem of computing non-trivial circuits in a vector matroid. To ...
- 56.6k
6
votes
1
answer
301
views
Orbits in commutative groups.
Let A be finite commutative group say $(Z_m)^h$. I will say that $S \subset A$ is an orbit if exist group $H$
which acts on A such that $S$ is an orbit of $H$.
Can one give a simple characterization ...
- 2,179
5
votes
2
answers
612
views
A Boolean function that is not constant on affine subspaces of large enough dimension
I'm interested in an explicit Boolean function $f \colon \{0,1\}^n \rightarrow \{0,1\}$ with the following property: if $f$ is constant on some affine subspace of $\{0,1\}^n$, then the dimension of ...
15
votes
3
answers
1k
views
Representation of vectors in $\mathbb{R}^2$ via differences of small vectors.
Is the following fact true?
Let $v_1,\ldots, v_k \in \mathbb{R}^2$, $\|v_i\|\leq 1$, be vectors that add up to zero. Does there exist a permutation $\sigma\in S_k$ and vectors $w_1,\ldots, w_k \...
- 1,284
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
4
votes
2
answers
442
views
A mapping from a lattice to itself
Consider $\mathbb{Z}^{n}$ for $n = 2^r$ where $r \geq 1$ . Look at the iterates of the following function $T$ from $\mathbb{Z}^n$ to itself.
$T((a_1, a_2, \ldots, a_n)) = (|a_1 - a_n|, |a_2 - a_1|, |...
- 73
11
votes
4
answers
5k
views
Maximum determinant of $\{0,1\}$-valued $n\times n$-matrices
What's the maximum determinant of $\{0,1\}$ matrices in $M(n,\mathbb{R})$?
If there's no exact formula what are the nearest upper and lower bounds do you know?
- 111
8
votes
1
answer
593
views
Representability of polymatroids over $GF(2)$
A polymatroid is a finite set $X$ and a rank function $d : P(X) \to {\mathbb N}$ such that
1) $d(\varnothing)=0$,
2) $A \subset B$ implies $d(A) \leq d(B)$, and
3) $d(A \cap B) + d(A \cup B) \leq d(...
- 25.5k
7
votes
1
answer
919
views
Association scheme on injective functions
This problem arises while studying the complexity of algorithms and I am quite unfamiliar with the subject.
Consider the set F of injective functions from {1..N} to {1..M}
we can define an ...
- 209
6
votes
2
answers
2k
views
Inner products and norms
Let $f:[n]\times [n] \rightarrow [0,1]$ be a function from pair of integers to the real interval [0.1]. I would like to find sets of complex vectors
$X= \{x_i\}$ and $Y=\{y_j\}$ satisfying $x_i\cdot ...
9
votes
1
answer
1k
views
(Elementary?) combinatorial identity expressing binomial coefficients as an alternating sum over permutations.
Background
I came up with this while trying to find a sort of high-level exposition of the exterior algebra of a vector space. Let $V$ be a vector space of dimension $n$ over $\mathbb{C}$, and let $...
- 8,559
12
votes
0
answers
349
views
Matroids with prescribed independent sets
Let $A$ be a finite set. Let $B$ be a family of subsets of $A$. We are interested in a matroid with a minimum rank such that every element of $B$ is independent. The answer is obvious - a uniform ...
- 1,791
13
votes
2
answers
1k
views
Combinatorial proof of (a special case of) the spectral theorem?
The spectral theorem for a real $n \times n$ symmetric matrix $A$ says that $A$ is diagonalizable with all eigenvalues real. If $A$ happens to have non-negative integer entries, it can be interpreted ...
- 118k
4
votes
1
answer
938
views
Random projection and finite fields
Suppose we have, say, $n$ $2n$-dimensional linearly independent vectors over $\mathbb{F}_2$. We do a projection on a random $d$-dimensional subspace. We are interested in probability that images of ...
- 1,791
14
votes
3
answers
872
views
How can we realize different combinatorial objects as the dimension of a construction on vector spaces? Are the resulting algebras useful?
Fix a vector space $V$ of dimension $n$ over some field $F$. Here are three commonly seen constructions:
its $k$th tensor power, $T^kV$, which has dimension $n^k$
its $k$th exterior power, $\Lambda^k(...
- 6,792
5
votes
0
answers
482
views
A class of determinants associated to Catalan-like Hankel determinants
The following matrices are related to some Catalan-like Hankel matrices. My question is whether direct computations of determinants of such matrices (i.e. without recourse to Hankel determinants) ...
- 5,622