All Questions
Tagged with determinants co.combinatorics
95 questions
27
votes
2
answers
1k
views
Some binomial coefficient determinants
It is well known that for $n>0$
$$d(n)=\det\left(\binom{2i+2j+1}{i+j}\right)_{i,j=0}^{n-1}=1.$$
Computer experiments suggest that more generally
$$d(n,k)=\det\left(\binom{2i+2j+2k+1}{i+j}\right)_{i,...
- 5,622
24
votes
2
answers
3k
views
A Putnam problem with a twist
This question is motivated by one of the problem set from this year's Putnam Examination. That is,
Problem. Let $S_1, S_2, \dots, S_{2^n-1}$ be the nonempty subsets of $\{1,2,\dots,n\}$ in some ...
- 43.2k
21
votes
2
answers
2k
views
Lifting matrices mod 2 to integers.
The following question was motivated by my research.
Consider a $n\times n$ matrix whose elements are $0$'s or $1$'s such that the determinant is odd. The question is: is it possible to assign signs ...
- 4,736
19
votes
2
answers
576
views
Eigenvalues and eigenvectors of the matrix with entries $\dbinom{n+1}{2j-i}$ for $i, j = 1, 2, \ldots, n$
Let $n$ be a nonnegative integer, and let $B$ be the $n \times n$-matrix (over the rational numbers) whose $\left(i, j\right)$-th entry is $\dbinom{n+1}{2j-i}$ for all $i, j \in \left\{ 1, 2, \ldots, ...
- 33.8k
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
17
votes
4
answers
2k
views
Possible values of the determinant for matrices with elements $\{1, 0, -1\}$
For matrices with elements $\{-1, 1\}$ it is known from here that the possible absolute values of determinants of $n \times n$, $n \leq 6$ matrices with entries $\{-1, 1\}$ are as follows:
...
- 539
14
votes
2
answers
873
views
"sinc'n determinant"
The function $\text{sinc}(x)=\frac{\sin x}x$ permeates mathematics and physics in several aspects, and it carries multiple presentations/formulations. My interest is to inject yet another one of such.
...
- 43.2k
14
votes
1
answer
1k
views
slick-proof-of-trick-for-counting-domino-tilings
The trick for rewriting the number of domino tilings of a simply-connected finite lattice region as the absolute value of the determinant of a matrix (due I believe to Kasteleyn and Percus, but if ...
- 19.7k
14
votes
3
answers
849
views
Determinant equal to Fibonacci sequence
I need to find the determinant of matrix defined by
\begin{align*}
& a_{i,1}=a_{1,j}=1,\quad \forall 1\leq i,j\leq n,\\ & a_{i,j}=a_{i-1,j}+a_{i,j-1}+i-j, \quad \forall 1< i,j\leq n.
\...
- 1,503
13
votes
1
answer
399
views
Is there a Giambelli identity with dual representations?
For natural numbers $a,b$ with $b\leq n-1$, let $V_{ (a|b)}$ be the irreducible representation of $GL_n$ with highest weight vector $(a+1, 1^b, 0^{n-b-1})$ where the exponentiation denotes repetition.
...
- 148k
13
votes
1
answer
385
views
Some more binomial coefficient determinants
The setup is similar to this question, but generalizes the size of the Hankel matrix. We'll define
$$d(n,k,r):=\det\left(\binom{2i+2j+k+r}{i+j}\right)_{i,j=0}^{kn-1}.$$
Edit: Thanks to Johann ...
- 13.4k
13
votes
1
answer
626
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,\...
- 2,552
12
votes
2
answers
780
views
Determinant of a checkerboard Hankel matrix with Catalan numbers
My goal is to compute
\begin{equation}
I = \det \left(\mathbf{I} + \mathbf{A}\right)
\end{equation}
where $\mathbf{A}$ is a $n \times n$ checkerboard matrix filled with Catalan numbers:
$$
\left\{
...
- 840
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
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
$?
- 171
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.
...
- 43.2k
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-...
- 26.5k
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 ...
- 43.2k
10
votes
2
answers
537
views
Prove that the matrix $[\Gamma(\lambda_{i}+\mu_{j})]$ is nonsingular
Let A is a $n\times n$ matrix given by \begin{align*} a_{ij} = [\Gamma(\lambda_{i}+\mu_{j})] \end{align*} where $0 < \lambda_{1} < \ldots < \lambda_{n}$ and $0 < \mu_{1} < \ldots < \...
- 233
10
votes
2
answers
4k
views
Determinant of a $3\times3$ magic square
This is my first question with mathOverflow so I hope my etiquette is up to par here.
My question is regarding a $3\times3$ magic square constructed using the la Loubère method (see la Loubère method)
...
- 103
9
votes
3
answers
409
views
Determinant of a block matrix with many $-1$'s
For an array $(n_1,...,n_k)$ of non-negative integers and non-zero reals $a_1,...,a_k$, define a block matrix $M$ of size $n=n_1+\cdots+n_k$ as follows:
The main diagonal has blocks of sizes $n_i$ and ...
- 13.4k
9
votes
2
answers
515
views
Minors of low rank skew-symmetric matrix
Let $A$ be an $n\times n$ skew-symmetric matrix of rank $r$.
Given subsets $X$ and $Y$ of row and column indices respectively, let $A_{X,Y}$ denote the submatrix of $A$ obtained by only keeping rows ...
- 557
9
votes
1
answer
349
views
A binomial determinant formula: a new variant
In a previous MO question, the OP asks a proof for $\det_{1\leq i,j\leq n}\left(\binom{i}{2j}+\binom{-i}{2j}\right)=1$. Subsequently, Gjergji Zaimi generalized the problem to
$$\det_{1\le i,j\le n}\...
- 43.2k
9
votes
0
answers
188
views
Cycles of length $2^n - 2$ in the De Bruijn graph
It is well known that the number of (cyclic) De Bruijn sequences is $2^{2^{n-1}-n}$. This number may also be interpreted as the number of cycles of length $2^n$ in the De Bruijn graph of order $n$.
...
- 82.7k
8
votes
2
answers
1k
views
Does there exist a nonsingular graph for which the determinant of its adjacency matrix remains the same upon deleting a vertex?
Consider simple graphs. Any simple graph $G$ is called nonsingular if its $(0,1)$-adjacency matrix $A(G)$ has nonzero determinant. Does there exist any nonsingular simple graph whose determinant value ...
- 640
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
8
votes
1
answer
406
views
Determinant of symmetric Latin square
Let $n=2m$ be an even number. Let us construct $n\times n$ symmetric matrices $S_n$ in the following way. The entries are indeterminates $X_1,\ldots,X_{n-1}$. We choose a $1$-factorization of the ...
- 52.3k
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
488
views
det(A)det(B) = det(AB+correction), Capelli identities, "factorized" representation of $\mathfrak {gl}_n$
Context: Some probably know that there are Capelli identities which state
$$det(A)det(B) = det(AB+correction)$$ for some matrices with non-commuting elements, they go back to the 19-th century, but ...
- 24.9k
8
votes
0
answers
512
views
Can one give a "nice" expression for this determinant?
I am asking this question on behalf of a senior faculty member who is sometimes intimidated by computers. It is motivated by a problem in invariant theory. Unfortunately the question is a bit vague.
...
- 40.2k
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
4
answers
1k
views
Generalized Cauchy-Binet sum over a fixed subset of indices
I originally posted this on math.stackexchange, but it quickly got buried. I removed it not too long after, thinking of rewriting it for MO, but I didn’t have a chance to post it until now. Apologies ...
- 13.6k
7
votes
3
answers
703
views
Distribution of sum of two permutation matrices
Determinant and permanent of sum of two $n\times n$ permutation matrices can be arbitrarily different.
What is the distribution of determinant of sum and difference of two $n\times n$ permutation ...
- 13.9k
7
votes
1
answer
462
views
On a problem for determinants associated to Cartan matrices of certain algebras
This is a continuation of Classification of algebras of finite global dimension via determinants of certain 0-1-matrices but this time with a concrete conjecture and using the simplification suggested ...
- 26.5k
7
votes
2
answers
818
views
Determinant of matrix with Stirling numbers as elements
After noticing that the determinant of an $n \times n$ matrix $A_n$ with elements $a_{i,j}=i^j$, $1 \le i \le n$, $1 \le j \le n$, is the superfactorial (product of the first $n$ factorials), I wanted ...
- 1,000
7
votes
1
answer
578
views
To compute minors of Jacobian of symmetric polynomials
For any $n$ tuple $f_1,f_2,\dots,f_n$ in the polynomial ring $\mathbb{C}[x_1,x_2,\dots,x_n]$
one has Jacobian, expressed by the $(n \times n)$-determinants:
$$
J(f_1,\dots,f_n):=|\frac{\partial}{\...
- 446
7
votes
0
answers
279
views
A conjecture about Hankel determinants of path generating functions
Let $a_{n,k}=a_{n,k}(x,c)$ be the generating function $\sum_P w(P),$ where $P$ runs over all paths from $(0,0)$ to $(n,k)$ consisting of horizontal steps $(1,0)$, up-steps $(1,1)$ and down-steps $(1,-...
- 5,622
7
votes
0
answers
220
views
Why are these two determinants equal?
This question is a follow up on Mark Wildon's comment from an earlier MO question.
As usual, let $(q)_k=(1-q)(1-q^2)\cdots(1-q^k)$ with $(q)_0:=1$. Also, define the Gaussian polynomials by
$$\binom{n}...
- 43.2k
6
votes
2
answers
1k
views
Determinant of the oriented adjacency matrix of a tree
Let $(V,E)$ be a finite oriented directed graph, with vertices and edges ordered, and $M$ the $|V|\times |E|$ matrix with entries
$$ m_{ve} = \begin{cases} 1 &\text{if $e$ points at $v$}\\
-1 &...
- 27.9k
6
votes
1
answer
208
views
Sum identities with immanants
For $\chi$ being an irreducible character of the symmetric group $S_n$ and being $M$ a complex $n\times n$-matrix, I would like to show
$$
\sum_{\sigma, \rho \in S_n} \overline{\chi(\sigma)} \chi(...
- 93
6
votes
2
answers
620
views
How large a subset of $\mathbb{F}_q^d$ can determine all determinants?
Denote by $\mathbb{F}_q$ a finite field with $q$ elements. For $\mathcal{P}$ be arbitrary subset of $\mathbb{F}_q^d.$ We define the set
$$S:= \left\{ \det([x_1,x_2,\dots,x_d]): x_1,x_2,\dots,x_d \in ...
user148117
6
votes
0
answers
219
views
Lindström-Gessel-Viennot from properties of the $Alt^k$ functor?
Let $A$ be the directed adjacency matrix of an acyclic directed graph, with variables as its nonzero entries (one for each edge). The $(a,b)$ entry of the matrix $(I-A)^{-1}$ is the sum over all paths ...
- 27.9k
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
6
votes
0
answers
349
views
Exact determinant of a Cauchy-like matrix
Question. Is there a closed-form expression for the determinant of a $n \times n$ matrix $A$ with entries
$$
A_{i,j} = \frac{1 - \delta_{i, j}}{z_i - z_j}, \qquad 1\leq i, j\leq n,
$$
where $z_i$ ...
- 263
5
votes
2
answers
312
views
minimum-maximum entries matrix
Let $M(n)$ be an $n\times n$ matrix in the variables $x_1,\dots,x_n$ with entries
$$M_{i,j}(n)=\frac{x_{\max(i,j)}}{x_{\min(i,j)}}, \qquad 1\leq i,j\leq n.$$
I'm interested in the following:
...
- 43.2k
5
votes
2
answers
635
views
Some curious Hankel determinants
Let $f(n,q)=\prod_{j=1}^na(q^j)$ for a polynomial $a(q)$ and let $d(n)=\det(f(i+j,q))_{i,j=0}^n$ be its Hankel determinant.
Computer experiments suggest that
$$\lim_{q\to1}\frac{d(n)}{(q-1)^\binom{n+...
- 5,622
5
votes
1
answer
251
views
Hankel determinants for q-Catalan numbers where q is a root of unity?
Let ${C_n}(q)$ be the weight of the Dyck paths of semilength $n$ where the upsteps have weight $1$ and the downsteps which end on height $i$ have weight $q^i$.
They satisfy ${C_n}(q) = \sum\limits_{j ...
- 5,622
5
votes
1
answer
408
views
An interesting Hankel determinant
Let $h(n,t) = \sum\limits_{j = 0}^n {\binom
{\lfloor {\frac{n}{2}} \rfloor }{j}\binom
{\lfloor {\frac{n+1}{2}}\rfloor }{j}t^j \\ }.$
I am interested in the Hankel determinants $${D_k}(n,t) = \det \...
- 5,622
5
votes
1
answer
169
views
An extension of Hadamard maximum determinant problem
Consider the Vandermonde product $\prod_{1\le j < k \le n} |z_j - z_k|$. It is well-known that under the constraint $|z_j| \le 1$ for all $j$, the product is maximized at a picket fence ...
- 4,466
5
votes
0
answers
190
views
Yet, another generalization of Catalan determinants
The discussion on this page is motivated by Johann Cigler's MO question. My intention arose from a possible generalization of Cigler's matrix
$$A_{n,m}=\left( \binom{2m}{j-i+m}-\binom{2m}{m-i-j-1} \...
- 43.2k