All Questions
Tagged with linear-algebra co.combinatorics
513 questions
8
votes
1
answer
623
views
A variant of an Eventown problem for modulo a prime number
Consider the following problem, called the 'Eventown problem':
In a town, residents can form different clubs. The town council establishes the following rules:
1) Every club must have an even ...
- 313
0
votes
0
answers
131
views
The largest size of a boolean subgraph (a hypercube) of a given graph
Let $G(\mathbb{F}_2^n)$ denote the graph that represents the lattice of all subspaces of $\mathbb{F}_2^n$ (also called a Hasse diagram). I am interested in knowing if there exists a large hypercube ...
- 313
1
vote
1
answer
321
views
Cycles of Permutation Related to Rectangular Matrix Transposition
let the entries of a rectangular matrix $A\in\mathbb{C}^{m\times n}; m,n\in\mathbb{N}$ be stored in row-order in a linear vector $v$, i.e. $A_{i,j}=v_{i*m+j}$
Question:
How can the first element ...
- 13.2k
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
13
votes
2
answers
913
views
Almost Hadamard matrices
As well-known, a Hadamard matrix is a square matrix with all coefficients $\pm 1$
and pairwise orthogonal rows or columns. Such matrices exist conjecturally
in every dimension divisible by $4$. Call ...
- 17.9k
7
votes
2
answers
2k
views
Linear independence of the square roots over Q
Does there exist a real number $a$ such that the numbers $\sqrt{n^2 + a^2}$ (for all natural $n$) are linearly independent over the field of rational numbers? It is evident that $a$ cannot be rational....
- 71
6
votes
0
answers
375
views
Kasteleyn, Gessel-Viennot and eigenvalues
The Kasteleyn matrix (for counting perfect matchings) and the Lindström-Gessel-Viennot matrix (for counting families of nonintersecting lattice paths) are tightly related, as observed many times by ...
- 1,343
9
votes
1
answer
543
views
On the number of polynomials that divide $x^{q-1}-1$ in some subspaces of $\mathbb F_q[x]$
Let $\mathbb F_q$ be a finite field (where $q$ is in general a power of a prime), and let $e, k$ be positive integers with $k \leq e < q-1$. Let $f_0(x), \ldots,
f_k(x) \in \mathbb F_q[x]$ be ...
- 307
11
votes
2
answers
1k
views
A binomial determinant fomula
Is there an existing or elementary proof of the determinant identity
$
\det_{1\le i,j\le n}\left( \binom{i}{2j}+ \binom{-i}{2j}\right)=1
$?
- 171
7
votes
1
answer
834
views
Equivalence of Hadamard Graph and Hadamard Matrix
I'm reading Distance Regular Graphs by Brouwer, Cohen, and Neumaier. In section 1.8, they explained Hadamard graphs.
Conversion from a Hadamard Matrix into a Hadamard Graph
An $n$-Hadamard graph $G$ ...
3
votes
1
answer
427
views
Ranks of higher incidence matrices of designs
In 1978 Doyen, Hubaut and Vandensavel proved that if $S$ is a Steiner triple system $S(2,3,v)$ then the $GF(2)$ rank of its incidence matrix $N$ is
$$
Rk_{2}(N)=v-(d_{p}+1),
$$
where $d_{p}$ is the ...
- 6,962
1
vote
1
answer
227
views
Do the cycles containing a fixed edge generate the cycle space of a graph?
Let $G$ be a $2$-connected graph and for $e \in E(G)$ denote by $\mathcal{C_e}$ the set of all cycles of $G$ containing the edge $e$.
For what set of edges does $\mathcal{C_e}$ contain a basis of the ...
- 1,034
9
votes
1
answer
420
views
Coherence between different ranking methods of a graph's vertices
Given a (connected) graph $G$ it is natural to want to rank its vertices, with the more "central" vertices ranked higher.
Two natural ways of doing it are:
By the degrees.
By the entries in a Perron ...
- 6,962
3
votes
3
answers
611
views
On MDS code property
Is there a code that is Maximum Distance Separable and not isomorphic to Reed Solomon Codes? When is a MDS code isomorphic to Reed Solomon Code?
Is there an easy test? If so, could someone provide ...
- 13.9k
3
votes
0
answers
562
views
Invariant subspaces of permutation matrix [closed]
Let $\sigma$ be a permutation matrix of order $n$. What are all the invariant subspaces of $\sigma$?
(I can only find 1 and n-1 dimensional subspaces)
Thanks in advance.
- 31
1
vote
1
answer
172
views
Linear combinations of basic cubes on a torus board
Consider an $n \times n \times n \times\dots\times n$ torus board of total size $n^k$ with $n > 4$ either even or odd.
Consider the basic cube of size $1 \times 1 \times \dots \times 1$ at a ...
- 13.9k
20
votes
3
answers
813
views
Basis removal gives a basis
Let $V$ be a vector space. Let us say that a finite set $X$ of vectors in $V$ is harmonic if for $B \subseteq X$,
$$
B \text{ is a basis of } V \implies X \setminus B \text{ is a basis of }V.
$$
Let ...
- 3,932
3
votes
1
answer
419
views
Maximal size of an almost-disjoint linearly independent family in $K^{\mathbb{N}}$
Let $K$ be a field, say infinite, and denote by $L$ the $K$-vector space $K^{\mathbb{N}}$. What is the maximal cardinality of a $K$-linearly independent subset $X$ of $L$ such that any two distinct ...
- 76
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
7
votes
3
answers
621
views
Reference for partial Hadamard matrices
Definition. An $m\times n$ matrix is said to be a partial Hadamard matrix (let's say PHM) if its entries are chosen from $\lbrace -1, 1 \rbrace$ such that the dot product of each pair of row vectors ...
- 2,075
3
votes
2
answers
2k
views
Invariants of Matrix Reordering
are there any invariants of matrices, that are not affected by row- and/or column permutations?
To me it seems that the sequence of singular values could be such an invariant; am I right, resp. are ...
- 13.2k
0
votes
0
answers
266
views
Finding the effective maximum number of subspaces in a finite dimensional vector space
Hi mathoverflow community, may be some one may give me a hint on the following problem before I spend much time on brute force search.
For $q$ a prime number and $n=6$, let $\mathbb {F}_{q}^{n}$ be ...
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
12
votes
1
answer
290
views
Largest subset of $GL_n(p)$ in which pairwise subtraction is also in $GL_n(p)$
Suppose $X\subset \mathrm{GL}_n(p)$ is a set of invertible matrices such that for every $A,B\in X$ then also $A-B\in \mathrm{GL}_n(p)\cup \{0\}$. (If anyone knows a name for such sets I would be ...
- 407
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
16
votes
0
answers
784
views
How to explain the picturesque patterns in François Brunault's matrix?
How to explain the patterns in the matrix defined in François Brunault's
answer to the question Freeness of a Z[x] module depicted below? --
Choosing colors according to the highest power of 2 which ...
- 19.6k
8
votes
1
answer
2k
views
Integer solution to special system of linear equations
This problem appear in my research, but I am unable to solve it.
There should be an easy argument, but I have not yet found it.
Informal version
An integer $k\geq 2$ is fixed.
We are given a matrix (...
- 15.8k
3
votes
1
answer
296
views
Question about the elementary divisors of a special matrix
I have the following question:
Is there a closed formula for the elementary divisors of the Matrix
$M=\lbrace (m_{ij})\rbrace_{i=1,...,n,\ j=1,...,k}$, where $m_{ij}$ is the greatest common ...
7
votes
2
answers
843
views
Dimension of incomplete matrix over finite fields.
Hi,
Suppose one has an incompletely specified $2^n \times 2^n$ matrix over some fixed finite field $\mathbb{F}_{p^k}$. In fact, one knows that the diagonal entries are zero and all other entries are ...
- 1,271
2
votes
1
answer
616
views
On solution of a class of discrete-time Lyapunov equation
Hello members, let's consider the following equation
$$X=F_{1}XF_{1}^{T}+...+F_{p}XF_{p}^{T}+C$$
where $p$ is an positive integer and $C$ is a known positive semidefinite matrix. If we augment $F=[F_{...
- 97
2
votes
1
answer
331
views
On solution of a discrete-time equation
Hello, members.
I have a problem for the following problem
when I derive an optimization algorithm for stochastic singular systems
$$S(k+1)=A(k)S(k)A^{T}(k)+R(k)+F(k)S(k+1)F^{T}(k)$$
where $R(k)>=...
- 97
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
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 ...
13
votes
1
answer
2k
views
Number of idempotent $n\times n$ matrices over $\mathbb{Z}/m\mathbb{Z}$?
Is there any known formula for the number of idempotent $n\times n$ matrices over $\mathbb{Z}_m:=\mathbb{Z}/m\mathbb{Z}$ ?
The number of idempotent matrices over a finite field is well-known and ...
user31416
9
votes
0
answers
464
views
An identity for Hankel determinants
Is the following result about Hankel determinants known or a simple consequence of some known results?
Let
$f(x) = \frac{\displaystyle 1}{{\displaystyle 1 - \frac{{a x^{m + 2}}}{\displaystyle {1 - \...
- 5,622
15
votes
1
answer
1k
views
Free subgroups of $\mathrm{GL}(2,\mathbb{Z})$
Is there a bound $B$ such that every 2-generator subgroup
$G = \langle a, b \rangle \le {\rm GL}(2,\mathbb{Z})$
whose generators do not satisfy a relation of length $\leq B$ is free?
If it exists, ...
- 19.6k
6
votes
2
answers
1k
views
Systems of simultaneous real quadratic equations
Starting from a problem in spectral graph theory, I got dragged into a problem in combinatorial matrix theory about constructing $n\times n$ real orthogonal matrices with a specified pattern of zero/...
13
votes
1
answer
516
views
Permanent of a matrix of odd integers
It is clear that the permanent of an $n\times n$ matrix which entries are odd integers, is an even number, as it is the sum of $n!$ odd numbers. I am interested in finding the highest power of $2$ ...
- 273
5
votes
1
answer
377
views
linear independence of finite binary sequences
Let $V_n=\{-1,1\}^n$ be the hypercube and let $C_n$ be a collection
$\{x_1,...,x_n\}$ of $n$ distinct elements of $V_n.$
Question: what is the smallest number $N(n)$ of non-zero vectors with integer ...
- 2,288
21
votes
0
answers
904
views
Cauchy matrices with elementary symmetric polynomials
$\newcommand{\vx}{\mathbf{x}}$
Let $e_k(\vx)$ denote the elementary symmetric polynomial, defined for $k=0,1,\ldots,n$ over a vector $\vx=(x_1,\ldots,x_n)$ by
\begin{equation*}
e_k(\vx) := \sum_{1 \...
- 28.6k
1
vote
1
answer
154
views
Optimal weights for large eigenvalues of Laplacian
For a weighted and directed graph $G$ on $n$ vertices we define the Laplacian matrix by $L(G) = D(G)-A(G)$. Here $(i,j)$-th entry of ${A(G)}$ equals the weight $w_{ij}$ of the edge from $i$ to $j$ if ...
- 397
11
votes
2
answers
797
views
Three half circles on the plane may not meet nicely
Let $H$ denote the union of the northern hemisphere of the unit circle $S^{1}$ with the interval $[-1,1]$ on the $x$-axis. That is, $H=\{(x,\sqrt{1-x^{2}}):-1\le x\le 1\}\cup\{(x,0):-1\le x\le 1\}$
...
- 2,136
11
votes
1
answer
265
views
What is the order of the largest subset of M_n(Z_p) such that no two elements commute?
Let $A(n,p)$ be the order of the largest subset of $M_n(Z_p)$ such that no two distinct matrices in this subset commute. Is it true that $\lim_{p \to \infty} \dfrac{A(n,p)}{p^{n^2}} =1$? Can anyone ...
- 413
9
votes
1
answer
611
views
Matrix-tree theorem via supersymmetry (i.e. Grassman algebras)
The matrix-tree theorem states the number of spanning trees of a graph $G$ is equal to a modified determinant of the adjacency matrix or "graph Laplacian", $\Delta_G$:
$$\#\{ \text{spanning ...
- 22.8k
15
votes
1
answer
777
views
Reconstructing a word
Let $w(a,b)$ be a word in two letter alphabet. Let $$A=\left(\begin{array}{lll}x_1 & x_2 & x_3\\\ x_4 &x_5 & x_6\\\ x_7 & x_8 & x_9\end{array}\right), B=\left(\begin{array}{lll}...
user6976
1
vote
0
answers
413
views
Combinatorial Interpretation of an Extension of Gaussian Polynomials
It is well-known that the Gaussian polynomial (or Gaussian coefficient, q-binomial coefficient) $\binom{n}{k}_q$ counts the number of $k$-dimensional subspaces of an $n$-dimensional vector space over $...
- 443
5
votes
2
answers
711
views
Maximum size of $k$-wise linearly independent set within $\lbrace 1, 2, 3, ..., u \rbrace^k$
Given a positive integer $u$, how many $k$-dimensional vectors whose coordinates are all in $\lbrace 1, 2, 3, ..., u\rbrace$ can you choose so that any $k$ of them are linearly independent? ...
- 53
1
vote
1
answer
157
views
Augmenting sub-spaces through a basis
Let $t \lt n-1$,
A family { $V_1, V_2, ..., V_n$ } sub-spaces of an $n$-dimensional vector space $V$ is called $t$-feasible if it satisfies conditions (i) and (ii) below:
(i) $\dim(V_i) = t$, for ...
- 1,034
31
votes
4
answers
2k
views
Probability of zero in a random matrix
Let $M(n,k)$ be the set of $n\times n$ matrices of nonnegative integers such that every row and every column sums to $k$. Let $P(n,k)$ be the fraction of such matrices which have no zero entries, ...
- 37.7k
0
votes
1
answer
148
views
Augmenting $t$-dimensional sub-spaces into $t+1$-dimensional sub-spaces through a basis
Let $V_1, V_2, ..., V_n$ be $t$-dimensional sub-spaces of an $n$-dimensional vector space $V$
where $t \lt n$.
Under what conditions the following would be true:
for any $B= \{v_1, v_2, ..., v_n\...
- 1,034