All Questions
Tagged with linear-algebra co.combinatorics
513 questions
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
1
vote
2
answers
171
views
Number of $k$-rank subspaces of $\mathbb{Z}_2^n$ is odd: easy proof?
Let $B(n, k)$ be the number of $k$-rank subspaces of $\mathbb{Z}_2^n$. One can establish $B(n, k) = {n \choose k}_2 = \frac{F(n)}{F(k)F(n - k)}$, where $F(x) = \displaystyle\prod_{i = 1}^x (2^i - 1)$. ...
- 5,590
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
4
votes
2
answers
208
views
Computation of the pfaffian of a particular matrix
This question was originally asked in (https://math.stackexchange.com/questions/4265063/computation-of-the-pfaffian-of-a-particular-matrix). I did not find any satisfactory answer there. So I am ...
- 493
4
votes
0
answers
152
views
How to show the set of stable polynomials equals to the set of Lorentzian polynomials in degree 2
Give a homogenous polynomial $f\in \mathbb{R}[x_1,\dots,x_n]$ of degree $2$ in $n$ variables, we can consider $f$ as a quadratic form.
We call $L_n^2:=$ the set of quadratic forms with nonnegative ...
- 41
1
vote
1
answer
223
views
Worpitzky-like identities?
Let $$r_k(x)=\prod_{j=1}^k {(\frac{x+j}{j}})^{\min(j,k-j)}.$$
Computations suggest that $$r_{2k}(x)=\sum_{j=0}^{(k-1)^2}a(2k,j)\binom{k^2+x-j}{k^2}$$ and $$r_{2k+1}(x)=\sum_{j=0}^{k^2-k}a(2k+1,j)\...
- 5,622
0
votes
0
answers
54
views
Rank decomposition of matrices over $\mathbb F_2$
Given an integer matrix $M\in\mathbb Z^{n\times n}$ of real rank $k$ what is the minimum and maximum number of rank $1$ matrices $B_1$ to $B_t$ we require so that $M\equiv\sum_{i=1}^tB_i\bmod 2$?
If $...
- 13.9k
2
votes
1
answer
385
views
Determinants of striped Hankel matrices
This question is related to the matrices described in Deyi Chen's recent MO post (look at some examples there). The main difference: we are asking for a determinant evaluation instead of a permanent, ...
- 43.2k
20
votes
2
answers
1k
views
Euler numbers and permanent of matrices
Motivated by Question 402249 of Zhi-Wei Sun, I consider the permanent of matrices
$$e(n)=\mathrm{per}\left[\operatorname{sgn} \left(\tan\pi\frac{j+k}n \right)\right]_{1\le j,k\le n-1},$$
where $n$ is ...
- 884
5
votes
1
answer
408
views
An interesting Hankel determinant
Let $h(n,t) = \sum\limits_{j = 0}^n {\binom
{\lfloor {\frac{n}{2}} \rfloor }{j}\binom
{\lfloor {\frac{n+1}{2}}\rfloor }{j}t^j \\ }.$
I am interested in the Hankel determinants $${D_k}(n,t) = \det \...
- 5,622
7
votes
0
answers
254
views
Set of unit vectors such that among any three there is an orthogonal pair
I was fascinated by the solutions of Problem 8 of the IMC 2021 contest, which can be summarized as:
Theorem 1. Let $v_1,\dotsc,v_N$ be distinct unit vectors in $\mathbb{R}^n$ such that among any three ...
- 105k
2
votes
1
answer
251
views
Dimension of circuit space of a matroid
If $G$ is a graph with edge set $E$, let $W$ be the $\mathbb{Z}/2$-vector space generated by the elements of $E$. If $A = \{a_1, \dots, a_n\} \subset E$, let $\bar{A} = a_1 + \dots + a_n \in V$; then $...
- 95
11
votes
2
answers
367
views
Kernel of a matrix and the Catalan numbers
Let $B_n$ denote the Boolean lattice of a set with $n \geq 2$ elements and $C_n$ the matrix with entries $c_{i,j}=1$ if $i \leq j$ and $c_{i,j}=0$ else, where $i,j\in B_n$.
Let $M_n:=C_n+C_n^T$ (this ...
- 26.5k
8
votes
1
answer
531
views
How large can the dimension of a 'Span of powers of a finite field basis' be?
Let $p$ be a prime. For finite field $\mathbb{F}_{p^k}$ and $d\in\mathbb{Z}^+$, I am considering the following quantity, where we interpret the field $\mathbb{F}_{p^k}$ also as a $\mathbb{F}_p$-vector ...
- 89
1
vote
1
answer
371
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
2
votes
2
answers
330
views
Polynomial time algorithm for rigid graph isomorphism
We found, implemented and tested algorithm
for graph isomorphism and it appears to be polynomial
time if the graph is rigid.
Q1 Is the algorithm below correct and polynomial time for rigid graphs?
A ...
- 25.4k
3
votes
1
answer
570
views
Magic circle (instead of magic square)
Motivation. I stumbled over this riddle (unfortunately in German): the goal is to fill the numbers $1\ldots7$ (or, equivalently, $0\ldots6$) into the $7$ little circles so that the sums of all numbers ...
- 48.9k
6
votes
0
answers
171
views
Eigenvalues of symmetric matrices associated to posets
For a finite connected poset $P$ define the Cartan matrix $C$ as the matrix with entries $c_{i,j}=1$ if $i \leq j$ and $c_{i,j}=0$ else, where $i,j\in P$.
Define the Frobenius-Cartan matrix of $P$ as $...
- 26.5k
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
2
votes
1
answer
430
views
At most one perfect matching of a bipartite graph
I. Given biadjacency matrix $A$ of a bipartite graph on $2n$ vertices having $n$ vertices of either color on the constraints the graph either has
$0$ perfect matchings
$1$ perfect matchings
is it ...
- 23
2
votes
1
answer
285
views
How many possible values for the determinant of an $n\times n$-matrix with entries $1,2,\dots,n^2$?
That is, to fill in an $n\times n$ matrix $M$ with all the first $n^2$ positive integers, how many different determinants $\det(M)$ could we get?
If the number is denoted by $f(n)$, is it an explicit ...
user178596
3
votes
1
answer
177
views
Products of Mersenne numbers as sums of real numbers
A Mersenne number is a number of the form $2^k-1$ for some $k \in \mathbb{N}$. Consider the set of $2^n-1$ products of Mersenne numbers
$$M_n=\left\{ \prod_{k\in S} (2^k-1) : S \subseteq [n], S\neq \...
- 980
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
4
votes
1
answer
209
views
Finding a binary variable assignment to make a matrix with variables singular (over F_p)
Consider a square matrix defined over a finite field $M\in\mathbb{F}_p^{n\times n}$ having the following form
$$M=\begin{bmatrix}a_{11}+b_{11}x_1&a_{12}+b_{12}x_1&\dots&a_{1n}+b_{1n}x_1\\...
- 153
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
7
votes
1
answer
326
views
Independent vectors in the permuting coordinates action of $S_n$ on $\mathbb{R}^n$
Let $V$ be the hyperplane in $\mathbb{R}^n$ with equation $\sum_i x_i=0$. The symmetric group $S_n$ acts on $V$ by $s\cdot (v_1,\ldots,v_n)=(v_{s^{-1}(1)},\ldots,v_{s^{-1}(n)})$. Consider those $v\in ...
1
vote
1
answer
172
views
Minimal volume of fundamental domains of lattices
Consider a full rank integer lattice in $\mathbb{R}^n$. Let $v_1$ be the shortest non-zero vector in the lattice, $v_2$ be the shortest one among those not parallel to $v_1$, $v_3$ be the shortest one ...
- 591
3
votes
1
answer
169
views
Obtaining an antichain from affine subspace
Suppose $a\in \{0,1\}^n$ and $S \subseteq \mathbb{F}_2^n$ is a subspace of dimension $d$. Define an affine subspace $S_a$ as follows:
$$S_a=\{a+x \mid x\in S\}.$$
What is the largest possible size of ...
- 171
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
4
votes
1
answer
317
views
On the real and finite field rank of a $0/1$ matrix - I
Let $M\in\{-1,0,+1\}^{n\times n}$ be a matrix of rank $r$.
Consider the matrix $f(M)\in\{0,+1\}^{mn\times mn}$ where $0$ in $M$ is replaced by $m\times m$ all $0$ matrix, $+1$ in $M$ is replaced by $m\...
- 13.9k
10
votes
2
answers
635
views
Largest set of $k$-wise linearly independent vectors in $\mathbb F_q^n$?
What is known about the largest set of $k$-wise linearly independent vectors in $\mathbb F_q^n$? I am especially interested when $q=2$, and in the regime where $k$ is fixed an $n\to\infty$. Here are ...
- 455
7
votes
2
answers
589
views
On a matrix problem in the field $\mathbb F_2$
Given $M$ a symmetric matrix in $\mathbb F_2^{n\times n}$ having $\mathsf{det}_\mathbb R(M)\neq0$ (non-singular in reals) and satisfying $PMP'=(M+J+I)$ or $P(M+J+I)P'=M$ where $P$ is 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
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
14
votes
1
answer
739
views
a Vandermonde-type of determinants summed over permutations
Let $S_n$ be the symmetric group. Consider
$$D:=\sum_{\sigma\in S_n} \text{sgn}(\sigma)\cdot \det\begin{pmatrix}1 & a_{\sigma(1)}-0 & (a_{\sigma(1)}-0)^2 & \cdots & (a_{\sigma(1)}-0)^{...
- 141
0
votes
0
answers
299
views
Question on rank of matrices over $\mathbb F_2$
$A$ is a square matrix in $\mathbb F_2^{n\times n}$ of rank $k\leq n-1$.
$B$ is a square matrix in $\mathbb F_2^{n\times n}$ of rank $n$.
$T$ is a square matrix in $\mathbb F_2^{n\times n}$ of rank $1$...
- 13.9k
1
vote
1
answer
153
views
Schur complement and depermuting an algorithm for $\mathsf{determinant}\bmod2$
Let $$M=\begin{bmatrix}A&B\\C&D\end{bmatrix}$$ be a matrix in $\mathbb F_2^{n\times n}$ where $A\in\mathbb F_2$ and $D\in\mathbb F_2^{(n-1)\times(n-1)}$ are square.
Through the determinant ...
- 13.9k
0
votes
1
answer
157
views
Generalization of Dickson's Lemma
Given $\{v^i\}_{i \in \mathbb{N}} \subseteq \mathbb{N}^n$, and $\cup_{k=1, \ldots, m} C_j = \mathbb{N}^n$ for some $m$, where each $C_k$ is a cone generated by rational vectors. My question is: does ...
- 37
-1
votes
1
answer
65
views
A follow-up question in a proof in a paper on complete multipartite graphs
A follow-up question from the following article/paper:
"Proof of a conjecture on distance energy change of complete multipartite graph due to edge deletion"
by Shaowei Sun and Kinkar Chandra ...
- 199
3
votes
1
answer
137
views
A question about a proof in a paper on complete multipartite graphs
I was recently reading the following article/paper:
"Proof of a conjecture on distance energy change of complete multipartite graph due to edge deletion"
by Shaowei Sun and Kinkar Chandra ...
- 199
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
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
1
answer
186
views
Enumerating binary matrices by $X$-ray sequences
Consider all $n\times n$ binary (entries are either $0$ or $1$) matrices, denoted $\mathcal{B}_n$.
Define the $X$-ray sequence of $A=(a_{ij})\in\mathcal{B}$ by $X(A)=x(1)x(2)\cdots x(2n-1)$ where
$x(k)...
- 43.2k
3
votes
3
answers
431
views
Given a positive integer $n$, some straight lines and lattice points such... Prove that the number of the lines is at least $n(n+3)$
I was trying to get an answer on MathSE long ago and now I got it.
Given a positive integer $n$ and some straight lines in the plane
such that none of the lines passes through $(0,0)$, and such that ...
- 237
3
votes
1
answer
374
views
Convergence on iterating a piecewise function
Given the four functions $P_1$, $P_2$, $N_1$ and $N_2$ (which together is a piecewise function) each with domain and range as shown above:
Is there an explanation as to why starting at any integer (...
- 143
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
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
11
votes
3
answers
591
views
Non-singular matrix with restricted entries
Given a set $S$ of integers with $1 \not\in S$, let us consider the set $\mathcal{M}$ of all the symmetric matrices $M$, such that:
All the diagonal entries of $M$ are equal to $1$.
All the off-...
- 571
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