All Questions
Tagged with linear-algebra co.combinatorics
513 questions
7
votes
1
answer
334
views
About a result on Hadamard matrix
I am currently reading "On Subsets with Cardinalities of Intersections Divisible by a Fixed Integer" by P. Frankl And A. M. Odlyzko. They used the following result without citation:
For each ...
- 281
0
votes
1
answer
146
views
Does the Plotkin bound mean that one can not achieve the Singleton bound asymptotically?
I am a little confused with the relationship between various bounds for error correcting codes.
Does the Plotkin bound mean that one can not achieve the Singleton bound asymptotically? That is, is ...
- 11
4
votes
0
answers
134
views
Irreducibility of polynomials associated to binomial coefficients
Let $n \geq 2$.
Let $M_n$ be the $(n+1) \times (n+1)$ matrix with entries $\binom{l}{k}$ for $0 \leq l,k \leq n$ and $U_n=M_n + M_n^T$ and let $f_n(x)$ denote the characteristic polynomial of $U_n$.
...
- 26.5k
0
votes
0
answers
133
views
On nilpotent singular $\mathbb F_2^{n\times n}$ matrices
Let $M$ be a $0/1$ matrix over $\mathbb F_2^{n\times n}$ with determinant $0$.
The set of such singular matrices form a semigroup.
The set of nilpotent matrices of size $n\times n$ form a semigroup.
...
- 13.9k
4
votes
0
answers
108
views
Doubly stochastic matrices that remain doubly stochastic after conjugating by the character table of a finite abelian group
I am curious if anything is known about the following.
Let $\Gamma$ be a finite abelian group, and let $\chi$ be its character table, normalized so that it is a unitary matrix. E.g., if $\Gamma$ is $\...
- 2,339
8
votes
1
answer
412
views
Big triples in a matrix
Consider an $n\times n$ real matrix $A=(a_{ij})$ with non negative entries. Assume that
- the sum of the three largest entries in each row is a constant $R$ (the same for all rows),
- the sum of the ...
- 5,103
3
votes
0
answers
85
views
Exterior powers of the Cartan matrix and Dyck paths
(This question can be formulated purely combinatorially in terms of Dyck paths, which is done in the second part of the question. But I am more interested whether this can be explained by some sort of ...
- 26.5k
18
votes
2
answers
488
views
Encoding primes via ranks of sign matrices
(Reposted from math.SE)
Recently I came across a very simply defined family of matrices: for $n \in \mathbb{N}$, set $A_n := (a_{ij})_{0 \le i, j \le n-1}$, where
$$\displaystyle a_{ij} := (-1)^{\big\...
- 281
3
votes
2
answers
176
views
Lower bound on the rank of a graph
[This has been edited in response to comments from Fedor Petrov]
Suppose that $n=dm$ with $d,m>1$. Consider an $n\times n$ matrix $M$ such that
All diagonal entries are equal to one
Each row has $...
- 56.9k
1
vote
0
answers
162
views
Number of full-rank binary matrices with given column Hamming weights [closed]
What is the number of $m \times n$ matrices over $\mbox{GF}(2)$ that share the following constraints :
They have full rank ($\mbox{rank} = m$, given that $m<n$).
Their columns have the given ...
- 111
8
votes
2
answers
528
views
Number of matrices with unit determinant and fixed sum of elements
Question. Let $\mathcal{M}_3$ be the set of $3\times 3$ matrices with non-negative integer entries and unit determinant. What is the number of $M\in \mathcal{M}_3$ with fixed sum of entries? What is ...
- 577
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
0
votes
1
answer
142
views
Vandermonde matrix with polynomials
Let us consider the simple Vandermonde matrix $V_n$ with $V_{ij} = \omega^{(i - 1)(j - 1)}$ where $\omega = e^{2i\pi/n}$. Its well known that for a column vector $A$, $VA$ is equivalent to evaluating ...
2
votes
1
answer
612
views
Inner product over finite field
sorry for informals but is my first post.
In Coding theory (exactly in Coding theory a first course - San ling and Chaoping) found this definition:
$\langle , \rangle :\mathbb{F}_q^n\times\mathbb{F}_q^...
1
vote
0
answers
336
views
Closed-form solution of a particular linear program
(Note: I asked a similar question at math.stackexchange but the present one is more precise.)
I have a linear program of the form:
$$\text{minimize} \space\space x_1 \space\space \text{subject to:}$$
$...
- 1,000
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$ ...
- 696
1
vote
0
answers
92
views
Rado graph and linear algebra
Let $V = \mathbb{Z}_{\geq 0}$ be the set of integers and let $\mathcal{G} = (V, E)$ be an (undirected) Rado graph on $V$. Let $W = \bigoplus_{i = 0}^{\infty} \mathbb{F}_2$ and write $x_i$ for the $i$-...
- 11
4
votes
1
answer
237
views
Intersection of the general linear group $\text{GL}_n(\mathbb{F}_q)$ and an affine subspace over a finite field
Let $\mathbb{F}_q$ be a finite field of $q$ elements, let $\text{M}_n(\mathbb{F}_q)$ be the vector space of $n \times n$ matrices over $\mathbb{F}_q$, let $\text{GL}_n(\mathbb{F}_q)$ be the group of $...
- 43
2
votes
0
answers
198
views
Intersection of subspace and subcubes
Consider a $d$-dimensional linear subspace $V\subseteq\mathbb{F}_p^n$, and its intersection with subcubes of form $S_1\times\cdots\times S_n$, where $S_1,\ldots,S_n$ are arbitrary size-$s$ subsets of $...
- 203
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
1
vote
2
answers
204
views
Only trivial solutions to system of linear diophantine equations possibly related to hamiltonian cycles in graphs
This might be related to counting hamiltonian cycles.
@Peter Taylor gave negative result about the one dimensional case, but we believe his attack is
not directly applicable to this question.
Given ...
- 25.4k
-1
votes
1
answer
825
views
How to calculate determinants of such types?
Consider next determinant that we want to expand around $h=1$
\begin{eqnarray}
Z_q \ = \ h^{N N_f} \ \ \left ( \prod_{n=1}^{N} \ \sum_{l_n=0}^{N_f -q} \ h^{2l_n+q} \ \binom{N_f}{l_n} \right ) \ \...
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
4
votes
3
answers
543
views
Determinant with factorials is not 0?
Below is a simple determinant. I need to show that it is not 0, so that the corresponding matrix is invertible.
$$
D = \begin{vmatrix}
0! & 1! & 2! & \ldots & x!\\
1! & ...
- 109
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
144
views
Given a binary parity check matrix, find a parity check matrix for the same code such that no row has weight greater than $k$
A parity check matrix for a binary linear code is a matrix $H$ (with linearly independent rows) such that the (right) kernel of $H$ is the codespace. Clearly we can replace any row $r_i$ by $r_i + \...
1
vote
1
answer
330
views
Determinants of Vandermonde -type matrix with mixed powers
A certain combinatorics problem requires finding the determinant of matrices like this:
\begin{equation}
\begin{bmatrix}
a & b & c & d & f \\
a^2 & b^2 & c^2 & d^2 & f^...
- 367
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
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
3
votes
2
answers
302
views
Vandermonde $V_n$ mod $n$
Consider the all-familiar Vandermonde determinant $V_n(x_1,\dots,x_n)$ of the matrix of $(i,j)$-entries $M_n(i,j)=x_j^{i-1}$ so that
$$V_n(x_1,\dots,x_n)=\prod_{1\leq i<j\leq n}(x_j-x_i).$$
Let's ...
- 43.2k
10
votes
1
answer
268
views
A bound for the permanent of a nonnegative matrix
Suppose $A=(a_{ij})$ is a symmetric (0,1)-matrix with 1's along the diagonal, and let $A_{ij}$ be the matrix obtained by removing the $i$-th row and $j$-th column.
Based on substantial numerical ...
- 105
10
votes
2
answers
473
views
Support of eigenvectors
Consider the $N$ by $N$ matrix
$$M_N= \begin{pmatrix} 1+3\lambda & -1-2\lambda & - \lambda & 0 & 0 &0 &0\\
-1-2\lambda & 2+3\lambda & -1 & -\lambda & 0 & 0 &...
- 192
1
vote
0
answers
150
views
Counting non-zero Gramians of Grassmanians over finite field
In case of $\mathbb{F}_{2}$, we can obtain the number of all reduced row echelon forms (so called Grassmannians) for some m$\times$n full rank matrices by the following gaussian polynomial,
$$
\binom{...
- 11
0
votes
0
answers
99
views
Invertible matrices with bounded nonnegative coefficients
I am teaching a class in linear algebra and I asked myself the following question: what is the chance to get an invertible matrix if I write a random one? My impulsive answer is "very likely"...
- 2,152
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
5
votes
1
answer
309
views
On a proof involving Young symmetrizers acting on tensor spaces
I hope this is not too elementary for this site, but I already asked something similar on MSE which has not received any attention whatsoever. I am extremely unfamiliar with the algebraic/...
- 3,292
0
votes
0
answers
56
views
Determining the total number of nonzero expansion terms in a (0,1)-matrix
Let $A=(a_{ij})_{n\times n}$ be a $(0,1)$-matrix such that it contains equal number of $1$s in each row and column. Is there any general method to count the total number of the nonzero terms $\prod_{i=...
- 133
1
vote
0
answers
111
views
$r(M)$-subsets of a 3-connected matroid $M$
It is proved in Lowrance, Oxley, Semple, and Welsh - On properties of almost all matroids that almost all matroids are 3-connected asymptotically. Also, it is conjectured that almost all matroids are ...
- 429
4
votes
1
answer
259
views
Why do these polynomials split almost in the middle?
Start with a palindromic sequence of integers $(a_0, a_1, \ldots, a_{n+1})$, i.e. $a_j=a_{n+1-j}$, and put $a_j:=0$ for $j<0$ and $j>n+1$. You may readily guess that the choice of the binomial ...
- 13.4k
11
votes
0
answers
541
views
How to determine the sign for the sum over all simple paths in the graph
$\DeclareMathOperator\perm{perm}\DeclareMathOperator\len{len}$Let $A$ be the adjacency matrix of a tree $T$ for some ordering $v_1,...,v_n$ of the vertices, and let $D=xI-A$ its characteristic ...
- 1,362
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
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
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
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
1
vote
0
answers
125
views
Determinants associated with Stern's diatomic sequence
Consider the so-called Stern's triangle (refer to these slides by R. Stanley), we denote here by $a_n(k)$. In an article Some linear recurrences motivated by Stern’s diatomic array, Stanley provided ...
- 43.2k
9
votes
0
answers
378
views
How many orthogonal matrices (not orthonormal) are there with entries in $\{0,1,−1\}$?
Here by orthogonal matrix I mean just the rows are mutually orthogonal. Two such matrices are equivalent if one can be obtained from the other by permutations of rows and columns, or change of signs ...
- 745
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
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
1
vote
1
answer
144
views
On parametrization of a type of unimodular $2\times2$ integral matrix
A matrix $\begin{bmatrix}w&x\\y&z\end{bmatrix}\in\mathbb Z^{2\times 2}$ is unimodular if $$|wz-xy|=1$$ holds.
Is there a parametrization of such matrices with $|w||z|-xy=1$
$$w,z<0<\max(...
- 13.9k
1
vote
0
answers
370
views
Combinatorial proof of a matrix equation
I'm looking for combinatorial proofs (using, e.g., trees) of the following particular matrix equation $(I)$ and also combinatoric operational analogs of its solution via matrix inversion and/or Cramer'...
- 10.5k