All Questions
38 questions
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}...
- 472
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
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 ...
- 43.2k
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
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,...
- 128k
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$,...
- 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(...
- 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 ...
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 ...
- 43.2k
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 ...
- 43.2k
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 ...
- 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:
...
- 38.6k
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 ...
- 150
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)!}.$$
...
- 43.2k
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 ...
- 696
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 ...
- 5,622
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
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 $...
- 43.2k
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 ...
- 696
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}$.
...
- 43.2k
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{...
- 43.2k
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 ...
- 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 ...
- 41
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}...
- 43.2k
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&...
- 43.2k
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 ...
- 43.2k
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 ...
- 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(\...
- 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=...
- 6,351
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, \...
- 43.2k
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-...
- 43.2k
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}
$$...
- 20.2k
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 ...
- 43.2k
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_{...
- 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 ...
- 43.2k
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 ...
- 5,898
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$ ...
- 43.2k
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\|_{...
- 439