6
votes
0answers
121 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 ...
0
votes
0answers
74 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 ...
0
votes
0answers
48 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 ...
0
votes
0answers
47 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 ...
6
votes
1answer
160 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 ...
7
votes
2answers
804 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 ...
3
votes
0answers
106 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 ...
6
votes
0answers
295 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 ...
10
votes
2answers
483 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 $?
3
votes
1answer
169 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$ ...
2
votes
1answer
101 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 ...
7
votes
0answers
181 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 ...
2
votes
0answers
128 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.
1
vote
1answer
154 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 ...
20
votes
3answers
663 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 ...
2
votes
1answer
338 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 ...
2
votes
0answers
309 views

A conjecture about vector space (repost from math.SE)

This post is copied from math.SE in the following link: http://math.stackexchange.com/questions/456398/a-conjecture-about-vector-space I have posted the question two days ago, but receive no answer ...
3
votes
1answer
112 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 ...
1
vote
2answers
187 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 ...
0
votes
0answers
206 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
0answers
116 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 ...
12
votes
1answer
249 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 ...
1
vote
0answers
84 views

Excluding linear size independent sets in graphs

What are some known criteria of excluding large independent sets (linear size) in k-regular graphs? I know one criterion is that the smallest eigenvalue of the adjacency matrix shouldn't be too small ...
12
votes
0answers
499 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 ...
6
votes
1answer
534 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 ...
3
votes
1answer
126 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 ...
6
votes
2answers
317 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 ...
2
votes
0answers
114 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 ...
4
votes
0answers
145 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 ...
8
votes
0answers
236 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 - ...
13
votes
1answer
507 views

Free subgroups of GL(2,Z)

Is there a bound $B$ such that every 2-generator subgroup $G = \langle a, b \rangle < {\rm GL}(2,\mathbb{Z})$ whose generators do not satisfy a relation of length $\leq B$ is free? If it exists, ...
4
votes
2answers
351 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 ...
12
votes
1answer
297 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$ ...
4
votes
0answers
154 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 coefficients ...
14
votes
0answers
361 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 ...
1
vote
1answer
95 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 ...
8
votes
2answers
456 views

Three half circles on the plane may not meet nicely

Let $H$ denote the union of the northen 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\}$ ...
11
votes
1answer
226 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 ...
6
votes
1answer
364 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 trees of ...
14
votes
1answer
655 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), ...
0
votes
0answers
220 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 ...
4
votes
2answers
291 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? ...
1
vote
1answer
136 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 ...
27
votes
4answers
1k 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, ...
0
votes
1answer
127 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, ..., ...
5
votes
1answer
402 views

Complexity of finding a 0-1 vector in a subspace or showing that there is none

This question, is a slightly different disguise (see below), came up in discussions of this question about equitable partitions A $0,1$ vector in $\mathbb{Z}^n$ is any vector with all entries $0$ and ...
45
votes
2answers
2k views

vector balancing problem

I believe the solution posted to the arXiv on June 17 by Marcus, Spielman, and Srivastava is correct. This problem may be hard, so I don't expect an off-the-cuff solution. But can anyone suggest ...
15
votes
3answers
591 views

Finding lots of discrete vectors in fairly general position

How many vectors can there be in $\mathbb{F}_2^{2n}$ such that no $n$ of them form a linearly dependent set? The bounds I have so far are embarrassingly far apart, though that probably means I should ...
1
vote
0answers
108 views

Counting equivalence classes in the transitive closure of two equivalence relations

Let $X$ be a finite set, and let $P_i$ and $Q_j$ be two partitions of $X$: $$\bigsqcup_i P_i = \bigsqcup_j Q_j = X.$$ The finest partition which is nevertheless coarser than both $P$ and $Q$ is ...
2
votes
1answer
103 views

Design constraint systems over the reals

This question is inspired by the discussion at this problem. Suppose I have a design consisting of a finite point set $U$ of size $|U|=m_{\emptyset}$ and a family of $n$ subsets (sometimes called ...