Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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 ...
Ross Snider's user avatar
15 votes
2 answers
861 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$...
Mare's user avatar
  • 26.5k
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, ...
Gjergji Zaimi's user avatar
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 ...
Deyi Chen's user avatar
  • 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 ...
Alexander Chervov's user avatar
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 ...
Tony Huynh's user avatar
  • 32.1k
12 votes
3 answers
784 views

Can the equation $1+z+z^2=z^n$ for natural $n$ have multiple complex roots $z$?

The question is stated in the title of this post. It is easy to see that, if $z$ is a multiple root of $p_n(z):=1+z+z^2-z^n$, then $(n-2)z^2+(n-1)z+n=0$, so that we can successively express $z^2,\dots,...
Iosif Pinelis's user avatar
11 votes
1 answer
579 views

Catalan determinants in search of a proof: Part II

This problem involves the Catalan numbers $C_n=\frac1{n+1}\binom{2n}n$. I can prove the below equality by computing each of the two sides, directly. That means, there is an algebraic proof. ...
T. Amdeberhan's user avatar
9 votes
0 answers
359 views

Factorisation of a polynomial from the Boolean algebra

Let $B_n$ denote the Boolean algebra of a set with $n \geq 2$ elements and $C_n$ the matrix with entries $c_{i,j}=1$ if $i \leq j$ and $c_{i,j}=0$ else, where $i,j\in B_n$. Let $M_n:=C_n+C_n^T$ and $...
Mare's user avatar
  • 26.5k
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, ...
27 votes
5 answers
2k views

Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?

Suppose we have a $(2m-1) \times (2m-1)$ matrix defined as follows: $$\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}.$$ For example, if $m=3$, the matrix is $$\begin{pmatrix}6 & 20 & 6& 0 ...
user42804's user avatar
  • 1,121
20 votes
1 answer
557 views

Almost orthogonal maps $f:\omega \to \{-1,1\}$

Let $\omega$ denote the set of non-negative integers. For sets $A,B$, let $B^A$ denote the set of maps $f:A\to B$. For $f,g\in\{-1,1\}^\omega$ we say that $f,g$ are almost orthogonal if there is $C_0\...
Dominic van der Zypen's user avatar
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 ...
Vagabond's user avatar
  • 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,\...
Seva's user avatar
  • 23k
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{$\...
Seva's user avatar
  • 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^{\...
T. Amdeberhan's user avatar
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): ...
11 votes
2 answers
558 views

Classification of algebras of finite global dimension via determinants of certain 0-1-matrices

I restrict to the elementary problem that is equivalent to give a classification when Morita-Nakayama algebras have finite global dimension (see the end of this post for some background). A Morita-...
Mare's user avatar
  • 26.5k
11 votes
1 answer
330 views

a Hankel matrix of involution numbers

Let $I_k$ denote the enumeration of involutions among permutations in $\mathfrak{S}_k$. I always enjoy these numbers. Of course, here is yet another cute experimental finding for which I ask validity. ...
T. Amdeberhan's user avatar
10 votes
3 answers
486 views

Distinguishing combinatorial maps by their linearizations

Every (not-necessarily invertible) map $f$ from $[n]:=\{1,2,,,,.n\}$ to itself determines a linear map $L_f$ from ${\bf R}^n$ to itself that sends the basis vector $e_k$ to $e_{f(k)}$ for $1 \leq k \...
James Propp's user avatar
  • 19.7k
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}=?$
Netanel's user avatar
  • 119
10 votes
1 answer
807 views

How many Lie and associative algebras over a finite field are there?

This question is related to the following general question: Given a variety of (non-associative) algebras $\mathcal V$, a finite field $\mathbb{F}_q$, with $q$ elements, and a positive integer $n$, ...
Thiago's user avatar
  • 398
9 votes
3 answers
356 views

Spectrum of orthogonality graph (2)

The orthogonality graph, $\Omega(n)$, has vertex set the set of $\pm 1$ vectors of length $n$, with orthogonal vectors being adjacent. I am only interested when $4|n$, since otherwise $\Omega(n)$ is ...
Clive elphick's user avatar
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&\...
T. Amdeberhan's user avatar
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 ...
Favst's user avatar
  • 2,075
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 ...
Alexander Chervov's user avatar
2 votes
0 answers
185 views

Infinite products from the fake Laver tables-Now with no set theory

We say that a sequence of algebras $(\{1,\dots,2^{n}\},*_{n})_{n\in\omega}$ is an inverse system of fake Laver tables if for $x\in\{1,\dots,2^{n}\}$, we have $2^{n}*_{n}x=x$, $x*_{n}1=x+1\mod 2^{n}$,...
Joseph Van Name's user avatar
1 vote
1 answer
223 views

Worpitzky-like identities?

Let $$r_k(x)=\prod_{j=1}^k {(\frac{x+j}{j}})^{\min(j,k-j)}.$$ Computations suggest that $$r_{2k}(x)=\sum_{j=0}^{(k-1)^2}a(2k,j)\binom{k^2+x-j}{k^2}$$ and $$r_{2k+1}(x)=\sum_{j=0}^{k^2-k}a(2k+1,j)\...
Johann Cigler's user avatar
11 votes
1 answer
627 views

One question on circulant $\pm1$ matrices

Let $n > 13$ be a positive integer. Is there any $n \times n$ circulant $\pm1$ matrix $A$ satisfying the following property $$AA^T=(n-1)I+J$$ where $I$ is the $n \times n$ identity matrix and $J$ ...
user369335's user avatar
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 ...
Mathew George's user avatar
17 votes
2 answers
1k views

Constructive proof of a rational version of Perron-Frobenius?

In the following, we work with vectors and matrices whose entries are rational numbers. Inequalities between such vectors are understood to be coordinatewise: e.g., two vectors $a = \left(a_1,a_2,\...
darij grinberg's user avatar
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-...
T. Amdeberhan's user avatar
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 ...
Jiahao Chen's user avatar
  • 1,890
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, ...
Stefan Kohl's user avatar
  • 19.6k
14 votes
2 answers
655 views

Number triangle

This question arose just out of curiosity. Note the triangle of 0-1's below, whose construction is as follows. Choose any number, say 53 as done here. The first line of the triangle is the binary ...
DSM's user avatar
  • 1,216
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(...
Zev Chonoles's user avatar
  • 6,792
13 votes
1 answer
311 views

Permanent of the Coxeter matrix of a distributive lattice

Let $L$ be a finite distributive lattice with $n$ elements. Let $C=(c_{x,y})$ be the $n \times n$ matrix with entry 1 in case $x \leq y$ and 0 else. The Coxeter matrix of $L$ is defined as the matrix $...
Mare's user avatar
  • 26.5k
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 ...
Analysis Student's user avatar
13 votes
1 answer
625 views

A difficult determinant

(EDIT: I have removed the denominators I had in a previous version as they were superfluous) The $N\times N$ determinant $$D(a,\vec{b})=\det\left((2N+a+b_j-i-j)!\right)$$ has the nice form $$D(a,\...
Marcel's user avatar
  • 2,552
13 votes
1 answer
468 views

Near-linear mappings from $\mathbb F_p$ to $\mathbb R$

$\newcommand{\F}{{\mathbb F}}$ $\newcommand{\R}{{\mathbb R}}$ $\renewcommand{\phi}{\varphi}$ Let $p\ge 5$ be a prime. If the functions $\phi_1,\phi_2,\phi_3\colon\F_p\to\R$ satisfy $\phi_1(x)+\...
Seva's user avatar
  • 23k
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 ...
Roland Bacher's user avatar
12 votes
2 answers
659 views

The $r$-dimensional volume of the Minkowski sum of $n$ ($n\geq r$) line sets

Let $n$ line sets be $\mathcal{S}_i=\{a\mathbf{h}_i:0 \le a \le 1\}$, for $1 \le i \le n$, where $\{\mathbf{h}_1,\cdots,\mathbf{h}_n\}$ is a vector group of rank $r$ in the $r$-dimensional Euclidean ...
RyanChan's user avatar
  • 550
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$,...
Andreas Thom's user avatar
  • 25.5k
11 votes
1 answer
315 views

Further aspects of a Hankel matrix of involution numbers

We have two conjectured generalizations of the question asked at a Hankel matrix of involution numbers by Tewodros Amdeberhan. Let $n!!=1!\,2!\cdots n!$. Conjecture 1. Let $I_k$ denote the number of ...
Richard Stanley's user avatar
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?
Igor Demidov's user avatar
11 votes
2 answers
1k views

A binomial determinant fomula

Is there an existing or elementary proof of the determinant identity $ \det_{1\le i,j\le n}\left( \binom{i}{2j}+ \binom{-i}{2j}\right)=1 $?
MPTuite's user avatar
  • 171
10 votes
2 answers
985 views

Determinantal symmetry: proof requested: Part I

Consider the determinantal function $$F(a,b,c):=\det\left[\binom{i+j+a+b}{i+a}\right]_{i,j=0}^{c-1}.$$ I would like to ask: QUESTION. Can you provide an argument, combinatorial or otherwise, to ...
T. Amdeberhan's user avatar
9 votes
1 answer
384 views

Smith Normal Form of a Cayley Graph of the Symmetric Group

Let $A_n$ be the adjacency matrix of the Cayley graph $\text{Cay}(S_n,C_n)$ where $C_n \subseteq S_n$ is the conjugacy class of $n$-cycles of the symmetric group $S_n$. Since the generating set of ...
Nathan Lindzey's user avatar
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 ...
Mehmet Aktas's user avatar
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 ...
Aaron Meyerowitz's user avatar