All Questions
Tagged with co.combinatorics matrices
88 questions with no upvoted or accepted answers
35
votes
0
answers
1k
views
Orthogonal vectors with entries from $\{-1,0,1\}$
Let $\mathbf{1}$ be the all-ones vector, and suppose $\mathbf{1}, \mathbf{v_1}, \mathbf{v_2}, \ldots, \mathbf{v_{n-1}} \in \{-1,0,1\}^n$ are mutually orthogonal non-zero vectors. Does it follow that $...
- 6,351
21
votes
0
answers
2k
views
The Fourier Transform of taking Eigenvalues
The purpose of this question is to ask about the Fourier transform of the map which associate to an $n$ by $n$ matrix its $n$ eigenvalues, or some function of the $n$ eigenvalues. The main motivation ...
- 24.7k
21
votes
0
answers
904
views
Cauchy matrices with elementary symmetric polynomials
$\newcommand{\vx}{\mathbf{x}}$
Let $e_k(\vx)$ denote the elementary symmetric polynomial, defined for $k=0,1,\ldots,n$ over a vector $\vx=(x_1,\ldots,x_n)$ by
\begin{equation*}
e_k(\vx) := \sum_{1 \...
- 28.6k
17
votes
0
answers
402
views
Number of $F_p$-matrices ac=ca, bd = db , ad - da = cb - bc is polynomial in p ? ("Manin matrix variety" - normal ? Cohen–Macaulay ? )
Consider four $n\times n$ matrices $a,b,c,d$ over finite field $F_q$ (or $F_p$ for simplicity), such that they satisfy three equations: $ac=ca,bd=db, ad-da=cb-bc $. Thus an affine algebraic manifold ...
- 24.9k
15
votes
0
answers
446
views
The rank of a "triangle-free" matrix
This is a version of the question I asked recently, but the assumptions got now strengthened substantially.
Suppose that $A=(a_{ij})_{1\le i,j\le n}$ is a square matrix with all elements in $\{0,\...
- 23k
13
votes
0
answers
188
views
Why is $ULU=NU$ (a refinement of $|N|=q^{n^2-n}$)?
Let $G=GL_n(\mathbb{F}_q)$, $U$, $L$, $N$ the subsets of upper-triangular unipotent, lower-triangular unipotent, all unipotent matrices respectively. Then $ULU=NU$ means that for any $g\in G$ the ...
- 3,772
13
votes
0
answers
1k
views
Pointwise (Hadamard) matrix product and the rank
$\DeclareMathOperator{\rk}{rk}$
Suppose that $A$ is a square matrix of order $n$. If, for any polynomials $P$ and $Q$ with $\deg P+\deg Q\le 2$, we have
$$ P(A)\circ Q(A^t) = P(1)Q(1)\, I_n \tag{$\...
- 23k
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
12
votes
0
answers
321
views
Combinatorial proof of invertibility of a symmetric matrix associated to the ring of matrices over a finite field
Let $F$ be a finite field of $q$ elements with characteristic $p$. Let $M_n(F)$ be the ring of $n\times n$ matrices over $F$. We define a $q^{n^2}\times q^{n^2}$ symmetric matrix $L$ over the ...
- 38.6k
11
votes
0
answers
253
views
Poset of nonvanishing minors of a matrix
This question was posed on MSE here three days ago, but hasn't gotten any answers or suggestions. I hope it's okay to ask it on MO, but if I should wait a little longer, please just let me know.
Say $...
- 6,237
9
votes
0
answers
270
views
The number of non-singular $n\times n$ matrices over $\mathbb{F}_2$ with exactly $k$ non-zero entries
Suppose $M_{n}^{k}$ is the number of non-singular $n\times n$ matrices over $\mathbb{F}_2$, that have exactly $k$ non-zero entries.
Is there some sort of formula to calculate $M_n^k$?
If $k < n$ ...
- 2,618
8
votes
0
answers
176
views
Nonzero subdeterminants conjecture: has anybody seen this anywhere?
I already posted this question on Mathematics StackExchange. A user there suggested that I rather post it on mathoverflow, since it is a research question. So here it is.
Let $m\geq2$, $n\geq1$ be ...
- 291
8
votes
0
answers
254
views
Quantum coupon collection: positivity of an alternating sum of matrices
It is well-known that in the classic coupon collecting problem (CCP), the expected waiting time is
\begin{equation*}
T_n(x_1,\ldots,x_n) = \sum_{k=1}^n (-1)^{k+1}\sum_{1\le i_1 < \cdots < i_k \...
- 28.6k
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
7
votes
0
answers
177
views
Matrix of high rank mod $2$: must it have a large non-singular minor (with disjoint rows and columns)?
Let $A$ be a $2n$-by-$2n$ matrix with entries in
$\mathbb{Z}/2\mathbb{Z}$ such that, for every $2n$-by-$2n$ diagonal
matrix $D$ with entries in $\mathbb{Z}/2\mathbb{Z}$, the matrix $A+D$
has rank $\...
- 20.2k
7
votes
0
answers
296
views
Counting 0-1 $n\times n$ matrices with a given rank r
What is the number $N$ of $n \times n$ $0$-$1$ matrices with rank $k$?
I read this sequence is
"OEIS A064230 Triangle $T(n,k)$ = number of rational (0,1) matrices of rank $k$ ($n\ge 0$, $0\le k\le ...
- 1,677
6
votes
0
answers
130
views
Bent vectors and $\pm 1$ eigenvectors with respect to non-Sylvester Hadamard matrices
A Hadamard matrix is an $n\times n$-matrix $H$ where each entry in $H$ is $\pm 1$ and where $H/\sqrt{n}$ is orthogonal. It is well-known that if $H$ is an $n\times n$-Hadamard matrix, then $n<3$ or ...
6
votes
0
answers
191
views
A curious $q$-identity
Let $[x]_{q}=\frac{1-q^x}{1-q}$ and $\binom{x}{n}_{q}$ denote a $q$-binomial coefficient.
Let $A_n(x,q)$ be the $n\times n $ matrix with entries $$q^\binom{i-j}{2}\binom{i+j+x}{i-j+1}_{q},$$ $0 \le i,...
- 5,622
6
votes
0
answers
336
views
Legendre's three-square theorem and squared norm of integer matrices
Let $\mathbb{N}$ be the set of non-negative integers. Let $E_n$ be the set of integers which are the sum of $n$ squares. Let $F_n$ be the set of integers of the form $\Vert A \Vert^2$ with $A \in M_n(...
6
votes
0
answers
375
views
Monomial base change and the Vandermonde
Denote the falling factorials by $(x)_k=x(x-1)\cdots(x-k+1)$.
The Vandermonde determinant is given by $\det\left[x_i^{j-1}\right]_1^n=\prod_{i<j}(x_j-x_i)$.
It is well-known that in as much as ...
- 43.2k
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
5
votes
0
answers
96
views
Partitioning the set of Pauli words into abelian pieces
Let $\sigma_x,\sigma_y,\sigma_z$ be the Pauli matrices. A Pauli word of length $n$ is defined as the tensor product $\otimes_{i=1}^n\sigma_i$ of operators $\sigma_1,\dots,\sigma_n\in\{\mathbf 1,\...
- 4,535
5
votes
0
answers
352
views
0-1 matrix combinatorial problem
Let $M \in \{0,1\}^{n \times n}$ and let $r_i$ be its $i$-th row. Given constant $p \in (0,1/2]$, let the number of $1$s in each row be at least $p\,n$. Given constant $c \in (0,1)$, what is the ...
- 1,677
4
votes
0
answers
262
views
Two questions about three circulant matrices
Consider the following matrix equation in $n \times n$ circulant $\pm 1$ matrices $A$, $B$, $C$
$$2AA^T+BB^T+CC^T=(4n+4)I-4J$$
where $I$ is the $n \times n$ identity matrix and $J$ is the $n×n$ matrix ...
- 696
4
votes
0
answers
94
views
Totally Unimodular matrix edited from ordinary matrix
Given a matrix $M\in\{0,1\}^{m\times n}$ is there an algorithm to tell if we can convert some of $1$s to $-1$s and make $M$ Totally Unimodular and output such a Totally Unimodular in polynomial in $mn$...
- 13.9k
4
votes
0
answers
355
views
Distribution of min/max row sum of matrix with i.i.d. uniform random variables
Given a $n\times n$ symmetric random matrix such that
all diagonal elements are all fixed as $1$.
all elements in upper triangle (excluding the diagonal) are i.i.d. uniform random variables ...
- 272
4
votes
0
answers
221
views
Extending a Theorem of Brualdi to Matrices with Infinitely Many Rows
This question is about extending a result on transportation polytopes from Brualdi regarding $m\times n$ matrices to the case when $m=\infty$.
Notation: Denote an $m\times n$ matrix by $A=[a_{i,j}]$, ...
- 329
4
votes
0
answers
188
views
Distributions over permutation groups $\mathcal{S}_n$
Partly inspired by recent developments in enumeration of pattern avoiding permutations, which is known to be connected with Brownian excursions [Hoffman&Rizzolo]. The exciting milestone is the ...
- 8,071
4
votes
0
answers
96
views
Are extremal tournament matrices always circulant or 'almost circulant'?
Define an antisymmetric 1-x-matrix as an $n\times n$ matrix $M=(m_{ij})$ with $m_{ii}=0$ and $\{m_{ij},m_{ji}\}=\{1,x\}$ for all $1\le i<j\le n$. Call their set $\mathcal A_n$.
The setup is as ...
- 13.4k
4
votes
0
answers
89
views
Can we replace 2-fold cover by n rectangles with 1-fold cover by n rectangles?
Suppose that $n$ rectangles cover every point of their union exactly twice (except for points on their boundaries).
Can we partition this union into at most $n$ rectangles?
I think it's pretty ...
- 18.8k
4
votes
0
answers
657
views
determinant of fibonacci-sum graphs
We have a simple graph with vertices $\{v_1, v_2, ... v_n\}$.
The adjacency matrix of this graph is $A= (a_{ij})$ so that
$a_{ij}=1$ if $i+j$ belongs to the Fibonacci sequence;
$a_{ij}=0$ ...
- 41
4
votes
0
answers
434
views
Smallest matrix covered by many random n by n matrices
We say that a matrix $M$ can be covered by a (smaller) matrix $N$ if every entry in $M$ is contained in some submatrix of $M$ that exactly equals to $N$, up to reordering the rows and columns of $N$. ...
- 51
4
votes
0
answers
351
views
Combinatorics of signed oriented graphs/skew-symmetric matrices
Consider a "complete" signed graph on $n$ vertices indexed by
$1,2,\dots,n$, that is, a graph in which any two distinct vertices $i$ and $j$ are connected by an oriented edge.
For each pair of ...
- 13.5k
3
votes
0
answers
85
views
Exterior powers of the Cartan matrix and Dyck paths
(This question can be formulated purely combinatorially in terms of Dyck paths, which is done in the second part of the question. But I am more interested whether this can be explained by some sort of ...
- 26.5k
3
votes
0
answers
148
views
Linear combinations of special matrices
I am a hobby computer scientist and I have a problem to which I am searching an efficient algorithm.
Given an integer n, we want to combine some square input-matrices of size n in a way that is ...
- 73
3
votes
0
answers
56
views
Is the outer automorphism group of a finite poset finite when the Coxeter matrix has finite order?
Let $P$ be a finite connected poset.
The Cartan matrix $C_P$ of $P$ is defined as the matrix with entries $c_{i,j}=1$ if $i \leq j$ and $c_{i,j}=0$ else for $i,j \in P$.
The Coxeter matrix of $P$ is ...
- 26.5k
3
votes
0
answers
155
views
Frobenius inner product of a zero line-sum matrix and a doubly stochastic matrix
Let $A$, $B$ be two $n\times n$ real matrices.
Let $A$ be a zero line-sum matrix where each row sum and each column sum equals zero, i.e., $$\sum_{i=1}^{n}a_{ij}=\sum_{j=1}^{n}a_{ij}=0 $$ (it seems ...
- 71
3
votes
0
answers
165
views
A combinatorial / geometric interpretation of compositional inversion via matrix inversion
There are several ways of finding the power or Taylor series for the compositional inverse of a function $f(x)$ with $f(0)=0\;$ given its series expansion, e.g., by using the classic Lagrange ...
- 10.5k
3
votes
0
answers
62
views
How likely is a matrix with exactly $n$ number $1$s per row to avoid a large wide empty submatrix?
Consider the finite collection $M(N,n)$ of all $N \times N$ matrices with exactly $n$ entries per row equal to $1$ and all other entries equal to zero $0$.
By an $a \times b$ submatrix of $M$ we ...
- 1,955
3
votes
0
answers
184
views
Matrices with only two different entries and maximal determinant
Define $\mathcal M_n$ as the set of all $n\times n$ matrices of full rank with each entry either 1 or $x$.
I am interested in how big the determinant of such a matrix can be. For this, we define in a ...
- 13.4k
3
votes
0
answers
118
views
Bounding the number of information sets in a linear binary code
A pretty well-known theorem regarding linear $(n,k,d)$ codes is that every $n-d+1$ coordinate positions contain an information set, but not all $n-d$ coordinate positions do. This is equivalent to a ...
3
votes
0
answers
317
views
Prime Hadamard matrices
Assume that $n$ is a sufficiently large number. Is there a Hadamard matrix $H_{4n \times 4n}=(h_{ij})$ with the last row and the last cloumn $J$ (thet is, for every $k$, $h_{k,4n}=1$ and $h_{4n, k}=1$)...
- 321
3
votes
0
answers
262
views
Matrix-tree for matrices with constant diagonal
I've got a symmetric matrix $A$ whose entries are in $\{0,-1,1\}$, with the diagonal entries all equal to $1$. I'm interested in finding a combinatorial description of the entries of the inverse of $A$...
- 6,962
2
votes
0
answers
113
views
Numbers of positive terms in polynomials equal A069999
Let $a(n)$ be A069999 (i.e., number of possible dimensions for commutators of $n \times n$ matrices; it is independent of the field). OEIS states that no generating function is known.
Let $P(n,k)$ be ...
- 4,938
2
votes
0
answers
71
views
Are the ranks of the following matrices given by these simple expressions?
The question itself is formulated in the title, so below I specify the matrices and expressions mentioned there. In case if this is something known or can be easily deduced from something known, this ...
- 321
2
votes
0
answers
78
views
Partitions of bent vectors
Let $H=\frac{1}{\sqrt{2}}\begin{bmatrix}1 & 1 \\ 1 & -1\end{bmatrix}.$ Let $A^{\otimes N}$ denote the tensor product of the matrix $A$ with itself taken $N$ times. We say that a vector $v$ of ...
2
votes
0
answers
148
views
Nilpotent polynomial matrices over $F_q$ - polynomial count variety ? ( Nilpotent cone for Hitchin-Gaudin like integrable system)
Context: Number of nilpotent $n\times n $ matrices over $F_q$ is $q^{n(n-1)}$ classical result due to Ph.Hall, M.Gerstenhaber (see very nice exposition by T.Leinster at n-cat-cafe/arxiv) which have ...
- 24.9k
2
votes
0
answers
203
views
Permutation similarity of matrices with many distinct entries
This is related to graph isomorphism.
Here matrices are square $n \times n$ with non-negative integer entries.
Two matrices $A,B$ are permutation similar if there exist
permutation matrix $P$ such ...
- 25.4k
2
votes
0
answers
54
views
Inverting "codimension matrix" for polytopes?
Let $P$ be an abstract polytope. Let's construct its square matrix $A$ as follows. Its lines and columns are labelled by all faces of $P$, of all dimensions. Put $A(F_1,F_2)=t^m$ if $F_1$ is a subface ...
- 765
2
votes
0
answers
119
views
Complete graph invariant based on integer programming?
Roughly speaking, we are trying to find complete graph invariant
as the lexicographically first matrix from the permutations
of the adjacency matrix.
Let $G$ be graph, possibly directed graph, of ...
- 25.4k