All Questions
Tagged with linear-algebra co.combinatorics
513 questions
1
vote
1
answer
224
views
OEIS Sequence A002846 and properties of matrix inverses
Sequence A002846 in https://oeis.org/A002846 (OEIS) gives, for each positive integer $n$, the number $a(n)$ of ways of transforming a set of $n$ indistinguishable objects into $n$ singletons via a ...
- 169
2
votes
0
answers
95
views
Maximal "all zeros" submatrix of a sparse binary matrix
Let $A\in\left\{ 0,1\right\} ^{M\times N}$, where each row of $A$ has at most $d$ components equal to $1$, and $d\leq M\ll N\ll Md$.
Question: $\forall n\leq N$, what is $m\left(n\right)$, the ...
- 968
2
votes
0
answers
957
views
The (minimum) rank of a relation
$\DeclareMathOperator{\rk}{rk}$
For an integer $n\ge 1$, let $\mathcal R_n$ denote the set of all reflexive binary relations on $[n]$. I define the rank of a relation $R\in\mathcal R_n$ to be the ...
- 23k
2
votes
1
answer
249
views
Existence of a permutation matrix on a restricted support
Let $\mathbf{A}\in\left\{ 0,1\right\} ^{d\times d}$, and $k(\mathbf{A})$ be the minimal number of $1$s in any column or row in $\mathbf{A}$.
Question: What is the minimal $k$ such that, for any $\...
- 968
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
4
votes
2
answers
239
views
Distribution of $0$-$1$ matrices
Consider $n\times n$ matrices with entries in $\{0,1\}$. The determinants of these ranges from $0$ to the Hadamard bound $\frac{(n+1)^{\frac{n+1}2}}{2^n}$. Assume $n$ is large enough.
What does the ...
- 309
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
19
votes
4
answers
719
views
The rank of a perturbed triangular matrix
$\DeclareMathOperator{\rk}{rk}$
The question below is implicit in this MO post, but I believe it deserves to be asked explicitly, particularly now that I have some more numerical evidence.
Suppose ...
- 23k
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
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
10
votes
0
answers
225
views
Cospectral mate of rhombic dodecahedron
I am wondering if the following pair of cospectral graphs was previously known.
The rhombic dodecahedron graph looks like this (graph6 string: 'M?????rrAiTOd_YO?'):
As far as I know, it was previously ...
- 2,339
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,\...
- 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{$\...
- 23k
4
votes
0
answers
309
views
A game played on binary matrices ($2$-dimension coin-turning game)
Let $r\geq 1$ be a natural number. I am interested in the following (two-player, impartial, perfect-information) game:
The state of the game is an $n\times n$ matrix with coefficients in $\mathbb{F}...
- 32.5k
0
votes
1
answer
28
views
Finding a point at which only certain linear functionals are integral
Let $C$ be a full-dimensional rational polyhedral cone in $\Bbb R^d$ with facets $G_1,\ldots,G_n$ . For each $i$, let $h_i$ be an integer-valued linear functional on $\Bbb R^d$ whose kernel is the ...
- 3,079
3
votes
1
answer
1k
views
Number of full-rank binary matrices with no rows of weight 1
For $m > n$, I want to calculate the number of binary matrices with $m$ rows and $n$ columns for which two conditions hold:
the rank of a matrix is $n$ (i.e. it is full-rank, as $m > n$);
there ...
- 367
1
vote
0
answers
119
views
An analogue of Hermitian matrix - does it exist?
Let $k$ be any field and $R\subseteq M_s(k)$ be a subring of $s\times s$ matrices over $k$. Identify $k$ with the scalar matrices, so that $k\subseteq R$. Let $A\in M_n(R)$ be an $n\times n$ matrix.
...
- 3,041
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
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 ...
- 50.8k
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. ...
- 43.2k
3
votes
0
answers
205
views
Probability of orthogonal vectors?
Denote $\mathcal I_m=\{-m,-m+1,\dots,0,\dots,m-1,m\}$ where $m\geq0$ is an integer.
Pick a uniformly random vectors $$\hat a=(a_n,a_{n-1},\dots,a_1)\in(\mathcal I_{m_1}+\sqrt{-1}\cdot\mathcal I_{m_2}...
- 13.9k
0
votes
1
answer
81
views
Can convex combinations of indicator functions for pairwise non-disjoint sets unordered by inclusion dominate one another?
Let $N$ be a finite subset of the naturals. Let $P$ be a set of subsets of $N$ such that:
1) $P\neq \varnothing$,
2) $\forall x\in P, |x| >1$,
3) $\forall x,y\in P,$ if $x\neq y$, then $x\not\...
- 3
0
votes
1
answer
250
views
Find the minimum distance of some bad binary code
Let $M$ be a $n \times n$ matrix over the finite field of two elements that satisfies the following property$\colon$ the total number of 1's in each row coincides with one in each column. In other ...
15
votes
1
answer
679
views
Submodules of $({\mathbb Z}/6{\mathbb Z})^n$ intersecting $\{0,1\}^n$ trivially
$\newcommand{\F}{{\mathbb F}}$
$\newcommand{\Z}{{\mathbb Z}}$
Suppose that $\F$ is a finite field of prime order $p:=|\F|$, and let $n$ be a positive integer. I consider the regime where $\F$ is ...
- 23k
6
votes
1
answer
328
views
Expanding into monomials
Given a multi-variable function $F$, denote the number of monomials by $N(F)$. For example, $N(x(x+y))=N(x^2+xy)=2$ and
$$
N(x(x+y)(x+y+z))=N(x^3+2x^2y+x^2z+xy^2+xyz)=5.
$$
Define the functions $f_n=...
- 43.2k
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
1
answer
503
views
does this set of permutations form a group? And more
Consider the group of $mn\times mn$ permutation matrices $\mathfrak{S}_{mn}$ and partition each such matrix $P$ into $n^2$ blocks of $m\times m$ matrices $Q_{i,j}$. Now, transpose each $Q_{i,j}$ (...
- 43.2k
1
vote
1
answer
171
views
transposing "unrimmed" permutations
Denote the set of $n\times n$ permutation matrices by $\mathfrak{S}_n$. The ordinary transpose preserves this group.
Given $P\in\mathfrak{S}_n$, construct the $n\times n$ matrix ${}^tP$ according to ...
- 43.2k
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^{\...
- 43.2k
3
votes
0
answers
142
views
Probability of hitting two vectors
Call an element of $ \{-m,\dots,0,\dots,m\}^{2^n}$ a vector. Assume $m = O(2^{2^n})$.
Let $u_1,u_2$ be vectors.
Let $\{v_1,\dots,v_{2^n}\}$ and $\{w_1,\dots,w_{2^n}\}$ be linearly independent ...
- 13.9k
2
votes
2
answers
717
views
The probabilistic method to find out a matrix is MDS
A matrix $M$ of order $n$ is an MDS
(Maximum Distance Separable)
matrix if and only if every sub-matrix of $M$ is non-singular.
For a matrix of order $n$, we should obtain $\sum_{i=1}^n \, {n \...
- 313
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 ...
- 1,121
1
vote
1
answer
394
views
On rank of random $0/1$ matrices
It is known that a $0/1$ matrix picked from uniform distribution from $\{0,1\}^{n\times n}$ is non-singular with probability $1-o(1)$.
Fix an integer $t$.
Consider a random matrix formed the ...
user94040
1
vote
1
answer
173
views
References request: reflections in coxeter groups
Let $V$ be a vector space. A reflection is a linear map $f: V \to V$ which has an eigenvalue $1$ with multiplicity $n-1$.
Let $S_n$ be the symmetric group on $\{1,\ldots,n\}$. Then the reflections in ...
- 6,201
1
vote
1
answer
121
views
Probability for high mutual coherence on all subsets of a Gaussian vector set
We examine as set of independent normal vectors:
$$ \forall i \in [N]\triangleq \{1,\dots,N\}:\,\mathbf{x}_{i}\sim\mathcal{N}\left(0,\mathbf{I}_{d}\right)$$
For any $\epsilon>0$ and $K\leq N$, we ...
- 968
1
vote
0
answers
226
views
Maximum number of mutually orthogonal $n$-bit sequences
What is the maximum number of mutually orthogonal $n$-bit sequences can we construct? And how to construct them? A trivial example is using the Hadamard matrix, but we can only build $n$ orthogonal $n$...
- 367
3
votes
1
answer
122
views
Inertia of the cone graph
Let $\widehat{G}$ be the graph obtained by adding a vertex to a graph $G$ and joining it to all vertices in $V(G)$. Let $\sigma(G)$ be the number of non-positive eigenvalues of the adjacency matrix of ...
- 3,463
1
vote
0
answers
75
views
Collections of vectors with a small scalar product
Consider $m$ unit vectors in $\mathbb{R}^n$ with positive coordinates so that $m>n$. How does one pick the $m$ unit vectors so that the largest inner product of them is the smallest?
- 2,288
2
votes
1
answer
303
views
Submatrix with small sum of elements
Let $A$ be an $n \times n$ matrix, for which I know the size of the sum of all its entries. Now I want to select an $m \times m$-submatrix, whose sum of entries is as small as possible. Is there any ...
- 2,207
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 ...
- 113
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 ...
- 305
2
votes
1
answer
325
views
Laplacian spectrum of directed network (digraph) and its complement
There is a well-known relation between the spectrum of graph laplacian and its complement's laplacian, namely
$$λ_j (G^c) + λ_{n+2−j} (G) = n\;,$$
where the eigenvalues $λ_j$ are sorted in ...
- 155
5
votes
0
answers
235
views
Riemann theta function inequality for a class of large random matrices
The following is essentially the same question as in this previous post, but since I have completely re-formulated it (hopefully for the better ;-), I decided to post a new question instead of an edit....
- 686
3
votes
0
answers
202
views
Difficult Gaussian-sum inequality for large random Bernoulli-Toeplitz matrices
I have come across the following problem in an attempt to prove an entropy bound for large random Bernoulli-Toeplitz matrices (Conjecture 1 on p. 16 of this preprint by Clifford et al. 2015), which is ...
- 686
5
votes
1
answer
564
views
When is the adjacency algebra of a graph an association scheme?
The adjacency algebra of a graph is the algebra consisting of all polynomials in the adjacency matrix of the graph. An association scheme is a commutative matrix algebra containing the identity and ...
- 2,339
3
votes
0
answers
171
views
Question about circulants and association schemes
Suppose $X$ and $Y$ are two $n$-circulants (Cayley graphs for $\mathbb{Z}_n$) with adjacency matrices $A_X$ and $A_Y$. Since they are circulants, both $X$ and $Y$ lie in some symmetric association ...
- 2,339
0
votes
0
answers
185
views
Sum of unit vectors always has a binary span after constrained permutations
Conjecture:
Let $e_1 = (1,0,\ldots,0), \ldots , e_{m_1+m_2} = (0,\ldots,0,1)$ be the unit vectors of the standard basis $E$ of $\mathbb{R}^{m_1+m_2}$.
An enumeration $ E \cup -E = \{f_1, \ldots, ...
- 121
1
vote
1
answer
433
views
Approximation of sets
Is the following true? For every $\varepsilon>0$ there is a finite
subset $W$ of $\mathbb{N}\times \mathbb{N}\times \mathbb{N}$, such that
$$|p_1(W)\cap p_2(W)\cap \{p_1(x)+p_2(x):x\in W\}\cap \{...
- 13
1
vote
1
answer
228
views
An extremal problem on matrices
Is it possible to determine (or give bounds for) the following extremal problem:
Let $k,m,r$ be positive integers such that $k,m \geq r$. What is the least number $n$ such that for any $r \times n$ ...
- 305
3
votes
0
answers
64
views
How many unimodular lattices does it take to fill a cube with high probability?
Consider $C_a$ in $\Bbb Z^n$ a cube of height $a$ at origin in positive coordinates with one corner at origin.
Consider the set $M_c$ of all unimodular matrices in $\Bbb Z^{n\times n}$ with each ...
- 13.9k