# Tagged Questions

**2**

votes

**2**answers

218 views

### Finding the set of all $0-1$ vectors in an affine subspace

We are given a $0-1$ matrix $A$ with constant row and column sum, and we need to find out if there exists a $0-1$ vector in the solution space of $Ax = \mathbf{1}$ over $\mathbb{Q}$ (or $\mathbb{Z}$) ...

**1**

vote

**0**answers

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

**0**

votes

**1**answer

143 views

### Kneser graphs eigenvalues

Basically, I want to prove that, in the Kneser graph (wikipedia has a good definition),$K_{n, m}$, if $n_{-}(A(G)) $ and $n_{+}(A(G))$ denote the number of negative and positive eigenvalues of A(G) ...

**4**

votes

**0**answers

88 views

### A question on hyperplanes in partial linear spaces and hypergraphs

A partial linear space (or a linear hypergraph) is a point line geometry $(P,L,I)$ where for every pair of points there is at most one line incident with both of them. A hyperplane in a partial linear ...

**2**

votes

**0**answers

257 views

### The twisted kiss of the curvaceous cubic and the staid tetrahedron (references)

(Migrated from MSE)
While investigating some operators, I came across some relations between the twisted cubic curve and the tetrahedron that link together some notions in differential geometry, ...

**0**

votes

**1**answer

67 views

### Collecting terms of a linear expression with nested sums and combinatorics in coefficients

I need to collect the $\Pr(\cdot)$ terms of the following expression:
$\sum_{m=3}^{n}\frac{g_{m}\left( \cdot \right) }{\left( \sqrt{\theta \left(
1-\theta \right) }\right) ^{m}}\left[ ...

**6**

votes

**0**answers

125 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

79 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

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

**1**

vote

**0**answers

50 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

169 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

848 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

123 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

301 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

497 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

192 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

128 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

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

**1**

vote

**0**answers

146 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

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

**19**

votes

**3**answers

668 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

341 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

312 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

122 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**

votes

**2**answers

206 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

210 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

120 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

251 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

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

**12**

votes

**0**answers

508 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

551 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

136 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

331 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

115 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

153 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

258 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

523 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

399 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

305 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

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

**15**

votes

**0**answers

407 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

99 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

464 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

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

**7**

votes

**1**answer

373 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

662 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

228 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

296 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

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