All Questions
Tagged with linear-algebra co.combinatorics
177 questions with no upvoted or accepted answers
4
votes
0
answers
124
views
Distributive lattices with periodic Coxeter matrix
Let $L$ be a finite distributive lattice and $U$ its incidence matrix with entries $u_{i,j}=1$ iff $i \leq j$ and $u_{i,j}=0$ else.
Then $U^{-1}$ is the Moebius matrix of $L$ and $C_L:=- U^{-1} U^{T}$ ...
- 26.5k
4
votes
0
answers
192
views
Forcing scalar products to avoid prescribed values
Let $p$ be a prime, and $n\ge 1$ an integer number. Suppose that the (not necessarily distinct) vectors $v_1,\dotsc,v_N \in{\mathbb F}_p^n$ satisfy the following condition:
\begin{gather}
\text{For ...
- 23k
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
94
views
Totally Unimodular matrix edited from ordinary matrix
Given a matrix $M\in\{0,1\}^{m\times n}$ is there an algorithm to tell if we can convert some of $1$s to $-1$s and make $M$ Totally Unimodular and output such a Totally Unimodular in polynomial in $mn$...
- 13.9k
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
4
votes
0
answers
137
views
Number of linearly independent subsets in arbitrary set
Consider $n$-dimensional vector space $\mathbb{F}_p^n$ over finite field $\mathbb{F}_p$ and a function $a: \mathbb{F}_p^n\rightarrow\mathbb{C}$. Let
$$ F(a) = \sum_{\substack{S\subset \mathbb{F}_p^n \...
- 331
4
votes
0
answers
287
views
Eigenvalues of "modified" Johnson scheme via the representation theory of the symmetric group
I am interested in eigenvalues of the following association scheme, which somewhat resembles the Johnson scheme.
Let $n$ and $k\leq n$ be positive integers.
The $n!/(n-k)!$ vertices of the scheme ...
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
0
answers
106
views
Bijectivity of a linear map between symmetric polynomials of even degree
Let $\mathfrak S_n$ be the symmetric group of permutations of $n$
letters and let $S = \sum_{\sigma\in\mathfrak S_n} \sigma$ be the
symmetrization operator.
Let $\Lambda_n^r$ be the vector space of ...
- 5,822
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
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
148
views
Linear combinations of special matrices
I am a hobby computer scientist and I have a problem to which I am searching an efficient algorithm.
Given an integer n, we want to combine some square input-matrices of size n in a way that is ...
- 73
3
votes
0
answers
75
views
Bunch of matrices with vanishing permanents
$\DeclareMathOperator{\Per}{Per}$
$\newcommand{\oI}{{\overline I}}$
$\newcommand{\oJ}{{\overline J}}$
Is it possible to classify pairs $(A,B)$ of square, nonsingular matrices over a field of prime ...
- 23k
3
votes
0
answers
56
views
Is the outer automorphism group of a finite poset finite when the Coxeter matrix has finite order?
Let $P$ be a finite connected poset.
The Cartan matrix $C_P$ of $P$ is defined as the matrix with entries $c_{i,j}=1$ if $i \leq j$ and $c_{i,j}=0$ else for $i,j \in P$.
The Coxeter matrix of $P$ is ...
- 26.5k
3
votes
0
answers
155
views
Frobenius inner product of a zero line-sum matrix and a doubly stochastic matrix
Let $A$, $B$ be two $n\times n$ real matrices.
Let $A$ be a zero line-sum matrix where each row sum and each column sum equals zero, i.e., $$\sum_{i=1}^{n}a_{ij}=\sum_{j=1}^{n}a_{ij}=0 $$ (it seems ...
- 71
3
votes
0
answers
124
views
Number of adjoint orbits containing a $(0,1)$-matrix
Motivated by this
question, what can be said about the number $f(n)$ of adjoint
orbits of $\mathrm{Mat}(n,\mathbb{C})$ (the ring of all $n\times n$
complex matrices) that contain a $(0,1)$-matrix? ...
- 50.8k
3
votes
0
answers
165
views
A combinatorial / geometric interpretation of compositional inversion via matrix inversion
There are several ways of finding the power or Taylor series for the compositional inverse of a function $f(x)$ with $f(0)=0\;$ given its series expansion, e.g., by using the classic Lagrange ...
- 10.5k
3
votes
0
answers
172
views
Equality of determinants: a direct justification request
Let $I_k$ denote the enumeration of involutions among permutations in $\mathfrak{S}_k$. Here is yet another cute finding for which I ask a:
Question. Is there a direct proof (or interpretation or ...
- 43.2k
3
votes
0
answers
142
views
Combinatorics question
Let $A = (a_{ij})_{1\le i,j\le h}$ be an $h$-by-$h$ non-degenerate upper triangular matrix with entry $a_{11} = 1$. Let $\Phi = \{\alpha_1,\alpha_2,\ldots,\alpha_d\}\subseteq \{1,2,\ldots,h\}=I$ be an ...
- 443
3
votes
0
answers
298
views
Matrix Inequality: Traces of $n$th powers
Let $A, B$ be matrices over $\mathbb{C}$ of the same dimensions (not necessarily square). With $'$ denoting conjugate-transpose, and tr the trace, show for $n\in\mathbb{N}$ that
$ 2\,\mathrm{Re}\, \...
- 131
3
votes
0
answers
182
views
Motivation/intution behind using linear algebra in these combinatorics problems
What is the motivation behind using linear algebra in these three problems ?
A pair $(m,n)$ is called nice if there is a directed graph with (self edge are allowed, but multiple edge are not allowed) ...
- 353
3
votes
0
answers
116
views
Trace of Symmetric matrices in fixed rank
I am solving some problem related to symmetric matrices over a finite field $\mathbb{F}_q$ and I am stuck at the following problem:
For every $a\in\mathbb{F}_q $, let $S_a(t,m)$ be the set of all $m\...
- 179
3
votes
0
answers
119
views
Forcing $A_1x,\dotsc,A_Kx$ to lie in a proper subspace
(This is a re-worked version of a question I asked several days ago.)
Let $J$ be the all-one matrix with $m$ rows and $n$ columns, and suppose that $J=A_1+\dotsb+A_K$ is a decomposition of $J$ into a ...
- 23k
3
votes
0
answers
91
views
Number of vectors such that the projection is decomposable
Let $V$ be a vector space of dimension $n\geq 6$ over the finite field $\mathbb{F}_q$. Let $\omega\in\bigwedge^{n-3}V$ be a nonzero element. Define the annihilator subspace of $\omega$ by $V_\omega=\{...
- 179
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
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
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
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
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
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
3
votes
0
answers
237
views
Multi-dimensional permanent of structured tensor
I am facing the multidimensional permanent
\begin{equation} \text{perm}(W) = \sum_{\sigma, \rho \in S_n} \prod_{j=1}^n W_{j, \sigma_j, \rho_j } \end{equation}
of a 3-tensor $W_{j,k,l}$ of ...
- 93
3
votes
0
answers
262
views
Matrix-tree for matrices with constant diagonal
I've got a symmetric matrix $A$ whose entries are in $\{0,-1,1\}$, with the diagonal entries all equal to $1$. I'm interested in finding a combinatorial description of the entries of the inverse of $A$...
- 6,962
3
votes
0
answers
527
views
3-SAT and a matrix of linear forms representing a non-degenerate matrix
This is a follow-up to the previous question on the same topic. Thanks to Emil Jeřábek I can now ask a more specific question.
As before, let $k$ be a field with $p$ elements. Consider the ...
- 3,897
3
votes
0
answers
390
views
Approximate action of unitary matrix with permutation matrix
Given a unitary matrix Q and a symmetric matrix B, I am trying to find a permutation matrix P such that
$ || QBQ^{T} - PBP^{T} ||_{F} $
is minimized.
The straightforward method of minimizing $ ...
3
votes
0
answers
212
views
Unique structures in a class of connected directed hypergraphs
Edit: The problem has been slightly revised, as I discovered that one of the questions I asked has an answer in the negative.
I'm working in a setting involving constraints on a system described by a ...
- 1,444
2
votes
0
answers
78
views
Partitions of bent vectors
Let $H=\frac{1}{\sqrt{2}}\begin{bmatrix}1 & 1 \\ 1 & -1\end{bmatrix}.$ Let $A^{\otimes N}$ denote the tensor product of the matrix $A$ with itself taken $N$ times. We say that a vector $v$ of ...
2
votes
0
answers
81
views
Degeneracy and the "Linear Degeneracy Testing" problem
The Affine Degeneracy problem is about deciding whether $n$ given points in $\mathbb{R}^d$ (or $\mathbb{Q}^d$) are "in general position". i.e. there is no $d+1$ tuple of points which lies in ...
- 153
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
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
2
votes
0
answers
110
views
Can the absolute value of fixed sized minors be arbitrarily ordered?
In an $m \times n$ matrix $X$, there are exactly $\binom{m}{r}\binom{n}{r}$ minors of size $r \times r$. Is it always possible to construct a real matrix $X$ such that the absolute value of the ...
- 263
2
votes
0
answers
352
views
Spectral norm bound for lower triangular matrix
Let $A$ be a $0/1$ square matrix which can be permuted to a non singular or a singular lower triangular matrix. Determinant is either $0$ or $1$. Can we provide tighter upper bounds on its spectral ...
- 13.9k
2
votes
0
answers
121
views
Number of cyclically symmetric tc-plane partitions vs a determinant
The ubiquitous Catalan numbers can be given by $C_0:=1$ and $C_{n+1}=\sum_{i+j=n}^nC_iC_j$.
In the same spirit, one may define the sequence $T_0:=1$ and $T_{n+1}=\sum_{i+j+k=n}T_iT_jT_k$ listed on ...
- 43.2k
2
votes
0
answers
99
views
Lower bound on iterated matrix application
Let $n \in \mathbb Z^2$ such that the non self-adjoint weighted Laplacian is
$$(\Delta u)(n)=u(n_1+1,n_2)-u(n_1-1,n_2) + i( u(n_1,n_2+1)- u(n_1,n_2-1))$$
the adjoint operator is then
$$(\Delta^* u)(n)=...
- 192
2
votes
0
answers
111
views
Forcing zero subset sums in zero characteristic
$\newcommand{\ve}{\varepsilon}$
A problem from the year 2003 Miklos Schweitzer exam (see also this MO post) goes, essentially, as follows:
If $b_1,\dotsc,b_k\in\mathbb F_p^n$ are vectors with $b_1^\...
- 23k
2
votes
0
answers
111
views
Inseparable field extensions of degree p and linear independence
Let $F$ be a field of characteristic $p$; let $\alpha \in F$ such that $\alpha \neq \beta^p$ for any $\beta \in F$, and let $K := F(x)$ where $x=\sqrt[p]{\alpha}$.
Is it true that the elements $1,(x-...
- 21
2
votes
0
answers
127
views
When an isometry is a hypercube symmetry?
Suppose that sequences $v_1,\ldots,v_m\in \{-1,+1\}^n$ and $u_1,\ldots,u_m\in \{-1,+1\}^n$ are isometric in $\mathbb{R}^n$, i.e. $u_j=Qv_j$ for some orthogonal matrix $Q$. What is the largest $m$ such ...
- 175
2
votes
0
answers
123
views
Mod $2$ of $\#PM(G)$ for arbitrary G?
Permanent mod $2$ of biadjacency gives polynomial time algorithm of $\#PM(G)\mod 2$ of perfect matchings of bipartite graph. Is there a similar efficient strategy for general graphs?
- 13.9k
2
votes
0
answers
185
views
Infinite products from the fake Laver tables-Now with no set theory
We say that a sequence of algebras $(\{1,\dots,2^{n}\},*_{n})_{n\in\omega}$ is an inverse system of fake Laver tables if for $x\in\{1,\dots,2^{n}\}$, we have
$2^{n}*_{n}x=x$,
$x*_{n}1=x+1\mod 2^{n}$,...