All Questions
Tagged with linear-algebra co.combinatorics
177 questions with no upvoted or accepted answers
2
votes
0
answers
126
views
Maximal number of $S_n$-conjugates living in a hyperplane
Let $v=(a_1,\dots,a_n)\in\mathbb{R}^n$ where the $a_i$ are distinct and positive. For $\sigma\in S_n$, let $\sigma(v)=(a_{\sigma(1)},\dots,a_{\sigma(n)})$. For any hyperplane $H$ through the origin, ...
- 21
2
votes
0
answers
86
views
A system of homogeneous linear equations
This is the "real-life" (but slightly more technical) version of a question I have asked recently.
For a prime $p>10$, let $\mathcal L_X$, $\mathcal L_Y$, and $\mathcal L_Z$ denote the pencils of ...
- 23k
2
votes
0
answers
41
views
Efficient $H$ representation of matrices with distinct cyclic shift permuted entries
Given points $v_1,\dots,v_n\in\mathbb Z^n$ in codimesion $1$ hyperplane $x_1+\dots+x_n=t$ with $0\leq x_{i}$ and a cyclic shift permutation $\sigma$ where
$v_1,\dots,v_n$ when written as columns of ...
- 13.9k
2
votes
0
answers
197
views
Full-rank factorization property of integer-valued matrices
$\newcommand{\al}{\alpha}
\newcommand{\de}{\delta}
\newcommand{\De}{\Delta}
\newcommand{\ep}{\varepsilon}
\newcommand{\ga}{\gamma}
\newcommand{\Ga}{\Gamma}
\newcommand{\la}{\lambda}
\newcommand{\Si}{\...
- 128k
2
votes
0
answers
90
views
Representable integer matrices
Let $C, R \in \mathbb{Z}^n$. If there is an $n \times n$-matrix $M$ with all entries being integers such that the sum of the entries of column $k$ equals $C(k)$, and the sum of the entries of row $k$ ...
- 48.9k
2
votes
0
answers
122
views
Number of distinct rows and columns in a matrix with bounded number of entries
How many distinct rows and columns a real square matrix can have (at least in symmetric case) such that rank of matrix is $r$ and entries:
are from $\{-b,-b+1,\dots,0,\dots,b-1,b\}$?
are from $\{-b,-...
- 13.9k
2
votes
0
answers
113
views
Complexity of tensor decomposition vector over $\Bbb F_q$ or $\Bbb Z$
Suppose we have a matrix $$T\in\Bbb K^{n^k\times m}$$ and a target vector $v\in\Bbb F_q^m$ where $m<n^k$ and $1<k$ holds.
We need to find $k$ vectors $u_1,\dots,u_k\in\Bbb K^n$ such that $$v=...
- 13.9k
2
votes
0
answers
363
views
Permanent of a matrix
Let $n \geq 2$ $a,b$ complex numbers (or in some other ring if you wish).
What is the permanent of the matrix
$$M(a,b,n)=
\begin{bmatrix}
a & a & a & ... & a & a \\
a &...
- 26.5k
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
0
answers
115
views
Polynomials with positive coefficients passing through fixed points/range of Vandermonde matrices
I'll give two equivalent statements of the setup, then give my questions.
Fix integers $M \leq N$ and define the Vandermonde-like matrix $V_{M,N}[i,j] = (1 - \frac{i}{M})^{j-1}$ for $i \in \{1,2,\...
- 21
2
votes
0
answers
395
views
A conjecture about vector space (repost from math.SE)
This post is copied from math.SE in the following link:
https://math.stackexchange.com/questions/456398/a-conjecture-about-vector-space
I have posted the question two days ago, but receive no answer ...
- 29
2
votes
0
answers
124
views
Products of matrices of a certain form
Are $n \times n$ matrices of the form
$$\pmatrix{1&1&1&1 \cr x&1&1&1 \cr x&x&1&1 \cr x&x&x&1}$$
studied anywhere? I am interested in the structure of ...
- 3,081
1
vote
0
answers
189
views
The existence of solutions to linear systems of equations over the integer ring $\mathbb{Z}$
There are already detailed results on the solutions of linear equations over fields, but I'd like to inquire about any good conclusions regarding the solutions of linear equations over the integer ...
- 173
1
vote
0
answers
72
views
Maximum trace of powers of symmetric $\{0,1\}$-valued matrix with fixed row and column sums
Maximize $\operatorname{tr}(A^k)$ over binary symmetric $n$ by $n$ matrices subject to $$a_{ii}=0, \sum_{j=1}^n a_{ij}=d, \sum_{i=1}^na_{ij}=d,$$
where $d,k$ are fixed positive integers.
I am having ...
- 11
1
vote
0
answers
329
views
The geometrical multiplicity of the nilpotent matrices
The following point is well-known in the literature.
Theorem. Let $A$ be a non-negative matrix in $M_n(\mathbb{R})$. If $A$ is nil-potent, there is a permutation matrix $P$ such that $P^tAP$ is ...
- 4,058
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
69
views
Convolutions of (m)-associahedra and (m)-noncrossing partition polynomials--combinatorial proofs?
I'm looking for combinatorial proofs of the convolutional identity COP below and its specializations I) and II).
(Edit 6/2/2023: A combinatorial proof is sketched in a blog post by Mike Spivey of a ...
- 10.5k
1
vote
0
answers
161
views
On an optimization question
Suppose we have a square matrix $M=(1-z)A+zB$ where $A,B$ have integer entries from $\{0,1\}$ with $\det(A)+\det(B)=1$ and $\det(A),\det(B),per(A),per(B)\in\{0,1\}$ and we want to find $z\in[0,1]$ ...
- 13.9k
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
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
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
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
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
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
1
vote
1
answer
376
views
A sequence and majorization
For two positive vectors $a,b$ such that $a\prec b$, we know that there is an $m$ sequence of vectors $c^{(i)}$ such that $$a\prec c^{(1)}\prec \ldots \prec c^{(m)}\prec b$$ where each vector in the ...
- 785
1
vote
0
answers
209
views
Solution to system of linear equations
Input: System of linear equations $$A[x_1,\dots,x_{t}]=b$$ where number of equations is at least number of variables but independence is not guaranteed. However there is atmost one non-negative ...
- 13.9k
1
vote
0
answers
88
views
On the real and finite field rank of a $0/1$ matrix - II
Let $M\in\{-\ell,\dots,-1,0,+1,\dots,+\ell\}^{n\times n}$ be a matrix of rank $r$ where $\ell\geq1$ such that there is a permutation matrix in $\{0,1\}^{m\times m}$ of order $2\ell$.
Fix a permutation ...
- 13.9k
1
vote
0
answers
127
views
Delocalization of eigenvectors of graph Laplacians
Let $(V,E)$ be an undirected, connected graph with $n$ nodes. The graph Laplacian is defined as $L = D - A$, where $D$ is the degree matrix and $A$ is the adjacency matrix. Let $0 = \lambda_1 < \...
- 41
1
vote
1
answer
310
views
Trees and spans of edge labels
Let $T$ be a rooted tree with $m$ leaves. Label every edge with a label of the form $x_i$ or $-x_i$, for some letter $x_i$. For each leaf in the tree, consider the formal linear combination $v$ ...
- 20.2k
1
vote
0
answers
131
views
On the order of the Coxeter matrix of a poset
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
1
vote
0
answers
75
views
Symmetric matrices of hyperbolic and elliptic type with certain kind of trace zero
I have been working on a problem related to determinantal varieties in symmetric matrices. I am stuck at the following point and would like to get some reference/help for the following question.
Let $\...
- 179
1
vote
0
answers
144
views
Simultaneous similarity classes of pairs in $\mathrm{GL}_{n}(\Bbb Z / p\Bbb Z)$?
$\DeclareMathOperator{\GL}{\operatorname{GL}}$Let $G$ be an elementary abelian $p$-group of rank $2$. Let $\alpha, \beta :G\rightarrow \GL_{n}(\Bbb Z / p\Bbb Z)$ be two injective homomorphisms. The ...
- 181
1
vote
0
answers
283
views
total unimodularity of a matrix
Let G be the node-arc incidence matrix of a given directed network (rows of $G$ correspond to nodes and its columns correspond to arcs). Let $B_1,\dots, B_K$ denote a partition of the nodes of the ...
- 393
1
vote
0
answers
130
views
Probabilistic lower bound on largest singular value of matrices
I have a distribution $\mathcal{D}$ that spits out vectors in $\{-1, 1\}^N$. Suppose I have a sample of $H$ of these vectors which I arrange into a matrix $M$ of the form $H \times N$.
Consider the ...
- 1,129
1
vote
0
answers
127
views
Lower and upper bounds of the distance between two Frobenius numbers
I consider two sequences of numbers: $A=\{a_1,...,a_{m-1},n\}$ and $B=\{n-a_{m-1},...,n-a_1,n\}$, where $a_1 < a_2 < ... < a_{m-1} < n$ and $\gcd(A) = \gcd(B) = 1$.
I investigate the ...
- 13
1
vote
0
answers
126
views
How many solutions to $p_i|a_{i,1} p_1 + \dotsc + a_{i,n} p_n$?
Consider a system of $n$ divisibility conditions on $n$ prime variables:
$$p_i|a_{i,1} p_1 + \dotsc + a_{i,n} p_n,\;\;\;\;\;1\leq i\leq n,$$
where $a_{i,j}$ are bounded integers. How many solutions ...
- 545
1
vote
0
answers
66
views
Spherical code for interesection of $k$-sparse vectors and unit sphere
Let us assume $X\in\mathbb{R}^{n\times d}, rank(X)=d$, integer $k\in\mathbb{N},k\ll d$, positive constant $0<\epsilon<1$, and $\mathcal{S}\subset \mathbb{R}^d$ denotes the unit sphere. We also ...
- 187
1
vote
0
answers
51
views
Relation between nullity of components to its parent graph
Let $G$ be an undirected graph and the corresponding adjacency matrix be $A$. Let $v$ be a cut-vertex of $G$. Let $G_1, G_2,\dots, G_k$ are the connected components of the induced graph $G-v$ ( the ...
- 640
1
vote
0
answers
55
views
Maximum number of matrices satisfying given rank conditions
Assume that we have $2k$ matrices $S_1,\ldots,S_k$ and $\Phi_1,\ldots,\Phi_k$ over some finite field $F$ such that
(i) $S_i\in F^{l/2\times l}$ and $\dim S_i=l/2$ for any $i\in\{1,\ldots,k\}$;
(ii)...
- 147
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
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
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
1
vote
0
answers
138
views
Minimum rank of certain matrices
Let $\mathscr{M}[n]$ be collection of $n\times n$ matrices with real entries from $\{0,1\}$ such that every row is distinct and every column is distinct.
What is minimum real rank of matrices in $\...
- 13.9k
1
vote
0
answers
54
views
Lattice-isotopic essentialization of arrangements
I'm working on a problem related to
$\textbf{Randell's isotopy theorem}$ for complex hyperplane arrangements. I have a question which seems quite obvious. However, I haven't found a rigorous proof ...
- 741
1
vote
0
answers
111
views
Notions of consistency / heterogeneity in sets of vector values?
The problem
Let us consider a row vector u of size $n\in\mathbb{N}$, containing only binary values (0,1):
$$u=(u_1 \cdots u_n), n\in\mathbb{N}$$
$$\forall i \in \{1\ldots n\}, u_i \in\{0,1\}$$
I would ...
- 11
1
vote
0
answers
53
views
Distributing partially known data between n parties
Assume that $n = 2r+1$. There are $n$ elements $a_1,a_2,\ldots,a_n$ from a finite field $\mathcal{F}$, and $n$ parties. Each party knows the values of at least $r+1$ elements out of those $n$ elements....
- 323
1
vote
0
answers
140
views
Reduce a Combinatorial problem
It is given n sets with k vectors. (k is element-wise positive or zero)
Choose one vector of each set so that the biggest element of the sum of the chosen vectors is minimal.
What i also know but is ...
- 11
1
vote
0
answers
64
views
A lower bound on the number of matrices whose image contains all multiples of $p^e$
Let $0\leq e<e^\prime$ be integers. Now suppose $N$ is the number of $n\times n$ matrices over the ring $R:=\mathbb{Z}/p^{e^\prime}\mathbb{Z}$ (where $p$ is prime) such that $(p^eR)^n\subseteq\...
- 1,305
1
vote
0
answers
272
views
"Stable" bounds on maximum size independent set in a graph
Suppose we have a graph $G=(V,E)$, and we want to upper bound $|I|/|V|$, where $I$ is the largest independent set in $G$. Then there is the Hoffman bound, which is $|I|/|V| \leq -\lambda_{min}/(\...
- 736