# Tagged Questions

**6**

votes

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

161 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

**2**answers

806 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

**0**answers

107 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

**0**answers

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

**2**answers

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

**1**answer

170 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

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

**3**answers

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

**1**answer

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

**0**answers

310 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

**1**answer

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

**2**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**2**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**2**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

**2**answers

457 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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**2**answers

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

**1**answer

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

**4**answers

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

**1**answer

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

**1**answer

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

**2**answers

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

**3**answers

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

**0**answers

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

**1**answer

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 ...