All Questions
Tagged with co.combinatorics matrices
55 questions
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
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
15
votes
2
answers
852
views
What are the periodic Dyck paths?
I changed the thread completely so that everything is now elementary linear algebra.
A Dyck path of length $n$ is a list of positive integers $[c_1,c_2,...,c_n]$ with $c_i -1 \leq c_{i+1}$ for all $i$...
- 26.5k
7
votes
1
answer
880
views
Bound for largest eigenvalue of symmetric matrices of uniform random variables over $[0,1]$ and fixed $1$s along diagonal and scattered $1$s
Given a $n\times n$ symmetric random matrix whose diagonal elements are all fixed as $1$. In addition, there are $k$ $1$s will be randomly scattered in upper triangular (of course, the corresponding ...
- 272
20
votes
2
answers
1k
views
Euler numbers and permanent of matrices
Motivated by Question 402249 of Zhi-Wei Sun, I consider the permanent of matrices
$$e(n)=\mathrm{per}\left[\operatorname{sgn} \left(\tan\pi\frac{j+k}n \right)\right]_{1\le j,k\le n-1},$$
where $n$ is ...
- 884
2
votes
1
answer
184
views
Count N-tuples of commuting matrices over $F_q$ is given by polynomials with pattern $\sum q^{A_i(N)} P_{i}(q) $, where $P_i$ - do not depend on $N$?
Count pairs of $k \times k$ commuting matrices over finite field $F_q$ is given by certain polynomials in $q$ (which is quite rare phenomena for algebraic varieties) and have interesting generating ...
- 24.9k
28
votes
3
answers
2k
views
Is every positive integer the permanent of some 0-1 matrix?
In the course of discussing another MO question we realized that we did not know the answer to a more basic question, namely:
Is it true that for every positive integer $k$ there exists a balanced ...
- 82.7k
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
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
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
14
votes
5
answers
989
views
Eigenvalues of a matrix with entries involving combinatorics
Let $F(n, l, i, j)$ be the cardinality of the set
\begin{eqnarray*}
\{(k_1, \cdots, k_n)\in\mathbb{Z}^{\oplus n}|0\leq k_r\leq l-1\text{ for }1\leq r\leq n\text{, }k_1+\cdots+k_n=lj-i\}.
\end{eqnarray*...
- 383
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
2
answers
697
views
in search of a transformation between determinants
Motivated by this MO question. Consider the two matrices $A_n$ and $B_n$ with entries $\binom{2j}i$ and $\binom{n+1}{2j-i}$, respectively; for $1\leq i, \,j\leq n$.
I can show $\det A_n=\det B_n=2^{\...
- 43.2k
8
votes
1
answer
1k
views
Is there an efficient algorithm to check whether two matrices are the same up to row and column permutations?
Define $\mathcal M_n$ as the set of all $n\times n$ matrices with each entry either 1 or $x$. Two such matrices are equivalent iff they can be obtained from each other by swapping pairs of rows and ...
- 13.4k
8
votes
1
answer
1k
views
Grassmann–Plücker relations for permanents
Let $K$ be a field, $1 \leq d \leq n$ integers and $V$ an $n$-dimensional vector space. The Grassmann–Plücker relations are quadratic forms on $\bigwedge^d V$ whose zero set is exactly the set of ...
- 24.7k
8
votes
1
answer
321
views
"Almost Hankelized" numerical Vandermonde
One of the more utilized determinant is that of Vandermonde's
$$\begin{vmatrix}
1&x_1&x_1^2&\dots&x_1^{n-1}\\
1&x_2&x_2^2&\dots&x_2^{n-1}\\
\ldots&\ldots&\...
- 43.2k
7
votes
1
answer
254
views
Eigenvectors of a matrix with entries involving combinatorics
In the question Eigenvalues of a matrix with entries involving combinatorics No_way asked about eigenvectors of $n\times n$ matrix $M$ with entries \begin{eqnarray*}
M_{ij}=(-1)^{i+j}F(n, l, i, j),
\...
- 12.3k
7
votes
3
answers
621
views
Reference for partial Hadamard matrices
Definition. An $m\times n$ matrix is said to be a partial Hadamard matrix (let's say PHM) if its entries are chosen from $\lbrace -1, 1 \rbrace$ such that the dot product of each pair of row vectors ...
- 2,075
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
3
votes
2
answers
453
views
Guess the next polynoms in the sequence (MO vs. AI :), count anticommuting $F_p$-matrices, P. Hrubeš conjecture
Here is a sequence of polynoms - (presumably) counting N-tuples of ANTI-commuting 2x2 matrices over $F_p, p>2$. (That is just the case of 2x2 matrices, and (surprisingly) it is not so easy to see a ...
- 24.9k
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
1
answer
308
views
Tangent numbers, secant numbers and permanent of matrices
Inspired by Question 402572, I consider the permanent of matrices
$$f(n)=\mathrm{per}(A)=\mathrm{per}\left[\operatorname{sgn} \left(\sin\pi\frac{j+2k}{n+1} \right)\right]_{1\le j,k\le n},$$
where $n$ ...
- 884
1
vote
0
answers
455
views
Possibility of Disconnected Subgraphs of a $k$ Connected $r$ regular Graph under a given condition
Context: Given a adjacency matrix A of a $r$-regular graph $G$ (not complete graph $K_{r+1}$) . $G$ is $k$ connected.
The matrix A can be divided into 4 sub-matrices based on adjacency of vertex $x ...
- 267
1
vote
1
answer
266
views
Combinatorial 0-1 vector problem
Let $M \in \{0, 1\}^{n\times n}$.
Given a constant integer $c \ge 2$, let the number of $1$s in each row be equal to $\frac{n}{c}$ (assuming $c$ is a divisor of $n$). Let $\mathcal{M}_c$ be the set of ...
- 1,677
0
votes
0
answers
61
views
Combinatorial counting question related to count (anti)commuting N-tuples of matrices (more generally $(X_1,...X_n): F(X_i,X_j)=0$ - only one F)
Consider some finite set $S$ (can be matrices over $F_p$), consider some symmetric relation $F(s1,s2)$ which values are True or False (for example - matrices (anti)commutate or not).
Question 1: can ...
- 24.9k
18
votes
3
answers
1k
views
Orthogonal matrices with small entries
Is it true that for any $n$, there exists a $n \times n$ real orthogonal matrix with all coefficients bounded (in absolute value) by $C/\sqrt{n}$, $C$ being an absolute constant ?
Some remarks :
If ...
- 4,653
18
votes
3
answers
1k
views
looking for proof or partial proof of determinant conjecture
Math people:
I am looking for a proof of a conjecture I made. I need to give two definitions. For distinct real numbers $x_1, x_2, \ldots, x_k$, define $\sigma(x_1, x_2, \ldots, x_k) =1$ if $(x_1, ...
- 533
17
votes
2
answers
911
views
Find the determinant of a matrix given the determinant of all $p\times p$ sub-matrices?
Is it possible to find the determinant of an $n\times n$- matrix, only given the determinant of all $p\times p$ sub-matrices in it? Here $p\leq n$ is fixed. This is obviously true if $p=1,n$. But what ...
- 293
17
votes
2
answers
1k
views
The GCD-matrix: generalizing a result of Smith?
Let $M$ be the $n\times n$ matrix, known as the GCD matrix, of entries $M_{ij}=\gcd(i,j)$. In the paper
H J S Smith, On the value of a certain arithmetical determinant, Proc. London Math. Soc. 7:208-...
- 43.2k
15
votes
7
answers
6k
views
Binary matrices with constant row and column sums
My question is about $m \times n$ binary matrices (aka $\{0,1\}$-matrices), whose rows all sum to the same value, and whose columns all sum to the same value (but these two values may be different).
...
- 878
15
votes
1
answer
1k
views
Free subgroups of $\mathrm{GL}(2,\mathbb{Z})$
Is there a bound $B$ such that every 2-generator subgroup
$G = \langle a, b \rangle \le {\rm GL}(2,\mathbb{Z})$
whose generators do not satisfy a relation of length $\leq B$ is free?
If it exists, ...
- 19.6k
13
votes
3
answers
746
views
Is there a row vector $x$ with integer entries such that no entry of $xM$ is $0 \text{ (mod }p\text{)}$?
Let $p$ be a prime and let $M$ be an $n \times m$ matrix with integer entries such that $M\vec{v} \not\equiv \vec{0} \text{ (mod }p\text{)}$ for any column vector $\vec{v} \neq \vec{0}$ whose entries ...
- 305
13
votes
2
answers
913
views
Almost Hadamard matrices
As well-known, a Hadamard matrix is a square matrix with all coefficients $\pm 1$
and pairwise orthogonal rows or columns. Such matrices exist conjecturally
in every dimension divisible by $4$. Call ...
- 17.9k
12
votes
1
answer
267
views
Total positivity of $q$-Pascal matrix?
A matrix of real numbers is called totally positive if all its minors are non-negative. A well-known example is the Pascal matrix $(\binom{i}{j})$.
Is it true that the minors of the $q$-Pascal matrix ...
- 5,622
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
11
votes
1
answer
636
views
A simple proof for a theorem of Szekeres and Turán
Szekeres and Turán found in 1937 a formula for the sum of the squares and the sum of the fourth powers of determinants of all $n$ by $n$ matrices with $\pm 1$ entries. (The sum of squares case follows ...
- 24.7k
11
votes
1
answer
467
views
Correspondence between matrix multiplication and a graph operation of Lovász
In his book "Large networks and graph limits", Lovász describes a multiplication operation (he calls it concatenation) on "bi-labeled graphs". An $(m,n)$ bi-labeled graph is a ...
- 2,339
8
votes
2
answers
502
views
Number of all different $n\times n$ matrices where sum of rows and columns is $3$
For a given positive integer $n$, I need to learn the number of $n\times n$ matrices of nonnegative integers with the following restrictions:
The sum of each row and column is equal to $3$.
Two ...
- 113
7
votes
1
answer
223
views
Result attribution for eigenvalues of a matrix of Pascal-type
A few years ago, I wanted to cite a result in a paper, for which I could not find a reference. I ended up not using the full strength of it, and the part that I needed could be easily proved. Still, I'...
- 1,190
7
votes
5
answers
1k
views
How to calculate one Cauchy type determinant
As we know, a Cauchy determinant of size n admits the following explicit formula:
$$\det \left(\frac{1}{x _i+y _j}\right) _{1\le i,j \le n}=\frac{\prod _{1\le i < j\le n} (x _j-x _i)(y _j-y _i)}{\...
- 113
7
votes
2
answers
443
views
Covering the zeros of 0/1 matrix with submatrices
The matrices I am dealing with are $n\times n$ of the following type (with $n=7$):
$M_7=\begin{pmatrix}1&0&0&0&0&0&1 \\ 1&1&0&0&0&0&0 \\ 0&1&1&...
- 115
6
votes
1
answer
500
views
Rank and frequency of permutations
(a) Let $[n] = \{1,\dotsc,n\}$, and let $\pi:[n]\to [n]$ be a permutation. Define an $n$-by-$n$ matrix $A=A(\pi)$ as follows: $A_{i,j}=1$ if $j>i$ and $\pi(j)>\pi(i)$, $A_{i,j}=-1$ If $j<i$ ...
- 20.2k
5
votes
3
answers
638
views
Invariants on matrices
Take all the $n\times n$ matrices of 0's and 1's and define an equivalence relation as follows: Two matrices are equal if there is a way to pass from the one to another by alternating the columns and ...
4
votes
1
answer
317
views
On the real and finite field rank of a $0/1$ matrix - I
Let $M\in\{-1,0,+1\}^{n\times n}$ be a matrix of rank $r$.
Consider the matrix $f(M)\in\{0,+1\}^{mn\times mn}$ where $0$ in $M$ is replaced by $m\times m$ all $0$ matrix, $+1$ in $M$ is replaced by $m\...
- 13.9k
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
3
votes
2
answers
316
views
Relation graph isomorphism to discrete logarithm
$\DeclareMathOperator\ora{ora}$Let $A_0$ be the adjacency matrix of graph $G$ and $P_0$
permutation matrix of multiplicative order $\rho$.
Let $X$ be positive integer and $B_0=P_0^X A_0 P_0^{-X}$.
Q1 ...
- 25.4k
3
votes
1
answer
204
views
A combinatorial matrix reconstruction problem
Given a positive integer $n$. For any symmetric $n\times n$ matrix $M$, write $M_{ik}$ for the $(i,k)$ entry, $M_k$ for the unordered list (multiset) of entries in row $k$, and $S(M)$ for the ...
- 3,873
3
votes
1
answer
1k
views
Number of full-rank binary matrices with no rows of weight 1
For $m > n$, I want to calculate the number of binary matrices with $m$ rows and $n$ columns for which two conditions hold:
the rank of a matrix is $n$ (i.e. it is full-rank, as $m > n$);
there ...
- 367
3
votes
1
answer
220
views
Number rank-k 0-1 matrices (characteristic 0)
What is the number of $n\times n$ 0/1-matrices with rank $k$?
(The rank is taken over the rationals.)
- 103
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