All Questions
Tagged with linear-algebra co.combinatorics
513 questions
8
votes
1
answer
811
views
(0,1)-matrix congruence: is it known?
[[UPDATE: This work has now been published at SIAM J Discrete Math.: Formulae for the Alon–Tarsi Conjecture.]]
By equating two formulae (one congruence by Glynn (1) (which has just appeared) and one ...
- 4,229
18
votes
3
answers
8k
views
Number of invertible {0,1} real matrices?
This question is inspired from here, where it was asked what possible determinants an $n \times n$ matrix with entries in {0,1} can have over $\mathbb{R}$.
My question is: how many such matrices ...
- 32.1k
18
votes
3
answers
6k
views
Number of unique determinants for an NxN (0,1)-matrix
I'm interested in bounds for the number of unique determinants of NxN (0,1)-matrices. Obviously some of these matrices will be singular and therefore will trivially have zero determinant. While it ...
- 359
56
votes
21
answers
14k
views
Linear algebra proofs in combinatorics?
Simple linear algebra methods are a surprisingly powerful tool to prove combinatorial results. Some examples of combinatorial theorems with linear algebra proofs are the (weak) perfect graph theorem, ...
81
votes
10
answers
9k
views
Existence of a zero-sum subset
Some time ago I heard this question and tried playing around with it. I've never succeeded to making actual progress. Here it goes:
Given a finite (nonempty) set of real numbers, $S=\{a_1,a_2,\dots, ...
- 85.6k
6
votes
1
answer
347
views
Sparse approximate representation of a collection of vectors
Suppose I have a collection of $n$ vectors $C \subset \mathbb{F}_2^n$. They are of course spanned by the canonical set of $n$ basis vectors.
What I would like to find is a much smaller (~ $\log n$) ...
- 583
9
votes
2
answers
2k
views
A generalization of Boolean matrix multiplication for order-3 tensors
The Boolean matrix product of two 0-1 $n \times n$ matrices $A$ and $B$ is the matrix $C$ defined as
$$C[i,j] = \vee_{k=1}^n (A[i,k] \wedge B[k,j]).$$ If $A = B$ and the matrix is an adjacency matrix ...
- 4,729
16
votes
3
answers
3k
views
A riddle about zeros, ones and minus-ones
I was asked this years ago, but I don't remember by whom, and have never managed to solve it.
Consider the $2^n \times n$ matrix of all vectors in {-1,1}$^n$.
Someone comes and maliciously replaces ...
- 435
11
votes
3
answers
2k
views
Matrices whose nullspace is nicely shaped
I'm looking for natural conditions on $a_{ij}$ to guarantee that the null space of the $n\times m$ matrix $A=(a_{ij})$ has a nice basis.
The null space of { {1,-2,1,0,0}, {0,1,-2,1,0}, {0,0,1,-2,1} } ...
- 9,756
5
votes
5
answers
4k
views
A random walk matrix has eigenvalue 1 with multiplicty 1 - why?
A random walk matrix has largest eigenvalue 1 with multiplicty 1 - why?
Let $G$ be a non-directed, regular connected graph with degree $d$. Let $A$ be its random walk matrix, i.e. it's adjacency ...
- 5,327
5
votes
1
answer
603
views
Hermite normal form in families
How does Hermite normal form (over $Z$) vary in families? I.e. if I have an $n\times m$ matrix $M$ whose entries are integral polynomials in some integral variable $x$, how does the Hermite normal ...
- 2,562
16
votes
5
answers
8k
views
Which graphs have incidence matrices of full rank?
This is a follow-up to a previous question. What graphs have incidence matrices of full rank?
Obvious members of the class: complete graphs.
Obvious counterexamples: Graph with more than two ...
- 1,890
7
votes
1
answer
2k
views
Graphs with incidence matrices whose pseudoinverses are proportional to their transposes
When I was working on my PhD dissertation, I came across a physical situation involving nodes and flows between them. It turned out that I was working with a complete oriented graph $K_n$ (all nodes ...
- 1,890