Skip to main content

All Questions

Filter by
Sorted by
Tagged with
18 votes
1 answer
635 views

Is Carlitz's paper correct about the number of similarity classes of commuting matrices?

L. Carlitz has a paper, Classes of pairs of commuting matrices over a finite field, that computes the number of simultaneous similarity classes of of pairs of commuting matrices in $\operatorname{Mat}...
Yifeng Huang'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
17 votes
1 answer
668 views

A coincidence or a fact: determinants of two matrices

While playing around with the MO question Determinant with factorials is not 0? about a determinant of the Hankel matrix of entries $(i+j-2)!$, having the value $\prod_{k=0}^{n-1}k!^2$, I stumbled on ...
T. Amdeberhan'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
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
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
8 votes
1 answer
593 views

Representability of polymatroids over $GF(2)$

A polymatroid is a finite set $X$ and a rank function $d : P(X) \to {\mathbb N}$ such that 1) $d(\varnothing)=0$, 2) $A \subset B$ implies $d(A) \leq d(B)$, and 3) $d(A \cap B) + d(A \cup B) \leq d(...
Andreas Thom's user avatar
  • 25.5k
7 votes
1 answer
299 views

Lipschitz-continuity of convex polytopes under the Hausdorff metric

Recently, I proved the following Lipschitz-continuity like result for convex polytopes: Let $A\in\mathbb R^{m\times n}$ and $b,b'\in\mathbb R^m$ be given such that $\{x\,:\,Ax\leq 0\}=\{0\}$ (which ...
Frederik vom Ende's user avatar
6 votes
1 answer
588 views

A numerical matrix of power sum polynomials

Let $p_i=x_1^i+x_2^i+\cdots+x_m^i=\sum_{k=1}^mx_k^i$ be the power sum polynomials. Then, the determinant of the $m\times m$ Hankel matrix $M_m=(p_{i+j-2})$, for $1\leq i,j\leq m$, has a neat ...
T. Amdeberhan's user avatar
6 votes
2 answers
339 views

Sum of divisors and LCM in determinants

$\newcommand{\lcm}{\operatorname{lcm}}$Let $\gcd(i,j)$ and $\lcm(i,j)$ be the greatest common divisor and least common multiple of the pair of positive integers $i$ and $j$. Denote the sum of divisors ...
T. Amdeberhan's user avatar
6 votes
1 answer
244 views

Linear independence over field of rational functions

To prove that functions $f_1(x), \dots, f_n(x)$ with $x \in \mathbb R$ are linearly independent, we only need to show that the Wronskian of these functions is non-zero at a certain value of $x$. Now ...
Pluviophile's user avatar
  • 1,608
6 votes
1 answer
257 views

Families of subsets whose characteristic vectors are spanning sets

Let $X$ be a finite set and $\mathbb CX$ be a vector space with basis $X$. If $Y\subseteq X$ is a subset, then by the characteristic vector of $Y$ I mean $\sum_{y\in Y}y$. My question is: ...
Benjamin Steinberg's user avatar
6 votes
1 answer
746 views

Relationship between spectral gaps of adjacency and Laplacian matrices of graphs

Let $G$ be an undirected simple graph on $n$ vertices, with self-loops allowed, and with arbitrary positive edge weights $w_{u,v}$ (which is $0$ if there is no edge between $u$ and $v$). Let $A$ be ...
Vilas Winstein's user avatar
6 votes
1 answer
237 views

Determinantal questions on Alternate Sign Matrices

Let $\mathcal{A}_n$ be the set of all Alternating Sign Matrices (ASM) of size $n\times n$. The cardinality $\#\mathcal{A}_n$ is well-known $$\#\mathcal{A}_n=\prod_{k=0}^{n-1} \frac{(3k+1)!}{(n+k)!}.$$ ...
T. Amdeberhan's user avatar
5 votes
1 answer
141 views

On the half-skew-centrosymmetric Hadamard matrices

Definition 1: A Hadamard matrix is an $n\times n$ matrix $H$ whose entries are either $1$ or $-1$ and whose rows are mutually orthogonal. Definition 2: A matrix $A$ is half-skew-centrosymmetric if ...
user369335's user avatar
5 votes
1 answer
213 views

Matrix-valued periodic Fibonacci polynomials

Consider the Fibonacci polynomials $f_n(x)$, defined by the recursion $f_n(x)=xf_{n-1}(x)-f_{n-2}(x)$ with initial values $f_0(x)=0$ and $f_1(x)=1$. It is well known that the values of these ...
Johann Cigler's user avatar
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} \...
T. Amdeberhan's user avatar
5 votes
0 answers
150 views

monomer-dimer tiling of a Young diagram

As a modest start, I propose the below problem for a special set of partitions. Perhaps it is known. Let $\lambda_n=(n,n-1,\dots,2,1)$ be the staircase partition and its corresponding Young diagram $...
T. Amdeberhan's user avatar
4 votes
1 answer
170 views

About $CW(512,16^2)$

Definitions: A weighing matrix $W = W(n,k)$ with weight $k$ is a square matrix of order $n$ and entries $w_{ij}$ in $\{0, \pm 1\}$ such that $WW^T=kI$, where $I$ is the identity matrix. A circulant ...
user369335's user avatar
4 votes
1 answer
239 views

Yet, another numerical variant of the Vandermonde matrix

In my earlier (soft) MO post, an elementary response was given by Ofir Gorodetsky in regard to the determinant of the symbolic counterpart to the numerical matrix $\mathbf{M}_n=(i^j-j^i)_{i,j}^{1,n}$. ...
T. Amdeberhan's user avatar
4 votes
0 answers
181 views

Fuss-Catalan: how does equality of these determinants hold?

There are many ways that the Catalan numbers seemed to have been generalized, one among them is through what Graham-Knuth-Patashnik (in Concrete Mathematics) dubbed as the Fuss-Catalan numbers $\frac1{...
T. Amdeberhan's user avatar
4 votes
0 answers
98 views

Ref. request: Enumerating elements of Bruhat cells

Given a field $F$ and a natural number $n$, let $B$ be the group of lower triangular, invertible $n \times n$ matrices over $F$. Then $$GL_n(F) = \biguplus_{\pi \in S_n} B \pi B,$$ where we embed the ...
Dirk's user avatar
  • 809
4 votes
0 answers
189 views

Slices of Simplices that are Simplices, Reference?

I am trying to find a reference for the following fact. It is elementary and not hard to prove, but I haven't been able to find the question treated anywhere. Let $A$ be an $l\times n$ matrix with ...
chris seaton's user avatar
3 votes
1 answer
165 views

The inverse of a symbolic matrix (with reciprocal binomials) has Laurent entries

Recalling the $q$-binomials (Gaussian polynomials). Let $[n]_q!=\prod_{j=1}^n\frac{1-q^j}{1-q}$ and $\binom{n}k_q=\frac{[n]_q!}{[k]_q!\cdot[n-k]_q!}$. Now, consider the $n\times n$ matrix $\mathbf{M}...
T. Amdeberhan's user avatar
3 votes
0 answers
185 views

"Circulant-Vandermonde" matrix: in search of a formula

An $n\times n$ circulant matrix $\mathbf{X}_n$ has the form \begin{align} \mathbf{X}_n= \begin{bmatrix} x_1 & x_2 & \cdots & x_{n-1} & x_n \\ x_2 & x_3 & \cdots & x_n&...
T. Amdeberhan's user avatar
3 votes
0 answers
207 views

On a variation of the Vandermonde matrix

The ubiquitous Vandermonde matrix, of entries $(x_i^{j-1})_{i,j}^{1,n}$, and its determinant $$\prod_{i<j}^{1,n}(x_j-x_i)$$ have found many utilities in Combinatorics and Physics, among other ...
T. Amdeberhan's user avatar
3 votes
0 answers
66 views

Classification or bounds on "totally symmetric" arrangements of subspaces

Let $F$ be a field and let $W_1, \dots, W_k \subset F^n$ be a collection of $d$-dimensional subspaces of $F^n$ such that $W_i \cap W_j = \{0\}$ for all indices $i,j$. We say that such an arrangement ...
Nick Salter's user avatar
  • 2,830
3 votes
0 answers
130 views

Where does this identity involving sums of Hankel-like determinants over partitions come from?

For a partition $\lambda=( \lambda_1,\dots,\lambda_n)\vdash n$ with $\lambda_1\ge\dots\ge\lambda_n\ge0$ and any function $f:\mathbb Z\to\mathbb C$, define a Hankel-like $n\times n$ matrix $$M_f(\...
Wolfgang's user avatar
  • 13.4k
2 votes
1 answer
460 views

Maximum permuted row/column sum of a matrix

Given a real $n \times n$ matrix $A$ (feel free to assume its entries are non-negative, if it helps), what is known about the problem of computing the quantity $$ \max_{\sigma \in S_n} \left\{\sum_{j=...
Nathaniel Johnston's user avatar
2 votes
1 answer
358 views

q-polynomials in terms of a basis

Consider the polynomials $$f_n(q)=\prod_{j=1}^n(1+q^j) \qquad \text{and} \qquad g_m(q)=1+q+q^2+\cdots+q^m.$$ I'll list a few examples to motivate my question. Direct calculations show that $$f_1=g_1, \...
T. Amdeberhan's user avatar
1 vote
1 answer
151 views

Counting monomials in skew-symmetric+diagonal matrices

This question is motivated by Richard Stanley's answer to this MO question. Let $g(n)$ be the number of distinct monomials in the expansion of the determinant of an $n\times n$ generic "skew-...
T. Amdeberhan's user avatar
1 vote
1 answer
76 views

Determinant formula for a certain parametrized M-matrix

Let $P_{ij}$ be variables, and let $A \in \mathbb{R}^{n\times n}$ be the matrix defined by $$ A_{ij} = \begin{cases} -P_{ij} & i \neq j,\\ P_{i1} + P_{i2} + \dots + P_{in} & i=j. \end{cases} $$...
Federico Poloni's user avatar
1 vote
1 answer
204 views

Interpret this matrix and its determinant

Let $n\geq1$ be an integer. Take the matrix $M(n)$, with entries, $M_{i,j}(n)=\sin\left(\frac{(i+j)\pi}2\right)$ if $i\neq j$ and $M_{i,i}(n)=x_i$. I wish to ask (this question has been modified from ...
T. Amdeberhan's user avatar
1 vote
1 answer
254 views

references for families of conditionaly negative definite matrices

We say that a matrix $A\in M_n(\mathbb{C})$ is a conditionaly negative definite matrix if it is hermitian and if for all complex numbers $c_1,\ldots,c_n$ such that $c_1+\cdots +c_n=0$ we have $$ \sum_{...
BigBill's user avatar
  • 1,222
1 vote
0 answers
158 views

Hankel transform of certain $\pm1$ sequences

The present discussion finds its motivation in the comments by Ira Gessel to my earlier MO question. More specifically, $$\prod_{i\geq0}(1-x^{2^i})=\sum_{k\geq0}(-1)^{s_2(k)}x^k$$ where $s_2(k)$ is ...
T. Amdeberhan's user avatar
1 vote
0 answers
229 views

Counting equivalence classes in the transitive closure of two equivalence relations

Let $X$ be a finite set, and let $P_i$ and $Q_j$ be two partitions of $X$: $$\bigsqcup_i P_i = \bigsqcup_j Q_j = X.$$ The finest partition which is nevertheless coarser than both $P$ and $Q$ is ...
John Wiltshire-Gordon's user avatar
0 votes
1 answer
129 views

A variant of numeric Vandermonde which failed symbolically?

Given some variables $x_1, x_2, \dots, x_n$, the Vandermonde determinant is given by $$V_n(x_1,\dots,x_n):=\det(x_j^{i-1})_{i,j=1}^n=\prod_{i<j}(x_j-x_i).$$ One can take as special cases: $x_j=j$ ...
T. Amdeberhan's user avatar
0 votes
0 answers
145 views

Bound on solutions of $Ax \ge b$

Let $A \in \mathbb{Z}^{m \times n}, b \in \mathbb{Z}^{m \times 1}$. One can show that if there is a solution of $Ax \ge b, x \in \mathbb{R}^n$ then there is one such that $\|x\|_{\infty} \le c (\|A\|_{...
user1868607's user avatar