5
votes
1answer
326 views

Lights out game

I would like to ask about the game Lights Out for a square nxn. In http://mathworld.wolfram.com/LightsOutPuzzle.html there is a list of the number of solutions to the game, and the number of solutions ...
6
votes
1answer
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 ...
3
votes
1answer
125 views

Number rank-k 0-1 matrices (characteristic 0)

What is the number of $n\times n$ 0/1-matrices with rank $k$? (The rank is taken over the rationals.)
18
votes
3answers
840 views

looking for proof or partial proof of determinant conjecture

Math people: I am looking for a proof of a conjecture I made. I need to give two definitions. For distinct real numbers $x_1, x_2, \ldots, x_k$, define $\sigma(x_1, x_2, \ldots, x_k) =1$ if $(x_1, ...
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 ...
7
votes
1answer
244 views

Combinatorics of resultants

This is a crosspost of http://math.stackexchange.com/questions/446470/combinatorics-of-resultants which received no answer. [EDIT: I deleted the initial copy of the question on MathSE]. Let ...
10
votes
1answer
347 views

A simple proof for a theorem of Szekeres and Turán

Szekeres and Turán found in 1937 a formula for the sum of the squares and the sum of the fourth powers of determinants of all $n$ by $n$ matrices with $\pm 1$ entries. (The sum of squares case follows ...
3
votes
2answers
581 views

A problem about Determinant of sum of permutation matrices

Let $w_1$ and $w_2$ be two permutations of $\{1, \cdots , k\}$ such that for all $1\leq i \leq k$, $w_1(i)\neq w_2(i)$. Let $m$ and $n$ be two relatively prime integers. Then is there exist two ...
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 ...
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 ...
12
votes
6answers
520 views

Invertibility of a certain matrix indexed by the Hamming cube

For reasons which the margin of this page is too small to hold, I have been reading parts of a recent paper by O. Selim On submeasures on Boolean algebras, arXiv 1212.6822v3 and in Section 7 the ...
5
votes
2answers
245 views

Semimagic Squares and Partitions

Say, we have a semimagic square $X$, that is, an $n\times n$ square matrix with entries from natural numbers, such that each row and column of it sums up to the same natural number $s$. Let $M$ be a ...
3
votes
0answers
418 views

determinant of fibonacci-sum graphs

We have a simple graph with vertices $\{v_1, v_2, ... v_n\}$. The adjacency matrix of this graph is $A= (a_{ij})$ so that $a_{ij}=1$ if $i+j$ belongs to the Fibonacci sequence; $a_{ij}=0$ ...
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, ...
15
votes
0answers
680 views

The Fourier Transform of taking Eigenvalues

The purpose of this question is to ask about the Fourier transform of the map which associate to an $n$ by $n$ matrix its $n$ eigenvalues, or some function of the $n$ eigenvalues. The main motivation ...
14
votes
0answers
362 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 ...
2
votes
3answers
762 views

How many matrices are possible for the given arrangement?

Given m & n, we have to find out the number of possible matrices of order m*n with the property that A(i,j) can be either 0 or 1 and that no contiguous sub-matrix of both length > 1 & breadth ...
3
votes
1answer
178 views

Historical question about MacMahon theorem, Wronski relation etc…

Seemingly the same fact goes under several names: MacMahon master theorem, Wronski relation, unnamed fact about symmetric functions - I wonder what is history and what should be ``correct name'' ? ...
4
votes
1answer
354 views

q-analog of the matrix exponential

I am a fan of the Matrix exponential $\exp(X)$, defined for any complex matrix $X$ by \begin{equation*} \exp(X) := \sum_{k \ge 0} \frac{X^k}{k!}. \end{equation*} I have a fleeting acquaintance with ...
1
vote
0answers
158 views

On so-called self-covering matrices

(In this discussion I'm assuming all matrices are binary (0/1-valued).) We say that a matrix $M$ can be covered by another matrix $N$ if every entry in $M$ is either (1) NOT contained in $N$, or (2) ...
1
vote
1answer
186 views

references for families of conditionaly negative definite matrices

We say that a matrix $A\in M_n(\mathbb{C})$ is a conditionaly negative definite matrix if it is hermitian and if for all complex numbers $c_1,\ldots,c_n$ such that $c_1+\cdots +c_n=0$ we have $$ ...
4
votes
0answers
406 views

Smallest matrix covered by many random n by n matrices

We say that a matrix $M$ can be covered by a (smaller) matrix $N$ if every entry in $M$ is contained in some submatrix of $M$ that exactly equals to $N$, up to reordering the rows and columns of $N$. ...
5
votes
1answer
293 views

Counting the (additive) decompositions of a quadratic, symmetric, empty-diagonal and constant-line matrix into permutation matrices

Dear community, I have the following combinatorial question which I will explain in short first and then with some more detail. At the end you will find a very simple example. Short version Le $A ...
19
votes
4answers
1k views

Matrices: characterizing pairs $(AB, BA)$

Let $A$ be an $m\times n$-matrix and $B$ an $n \times m$-matrix over the same field. Consider the matrices $C=AB$ and $D=BA$. It is probably well known (and not difficult to show) that the only ...
3
votes
2answers
276 views

Partitioning a matrix with bounded row sums

Let $A$ be a $n \times n$ matrix with non-negative entries $a_{ij}$, where $a_{ij}$ is the entry in the $i^{th}$ row and $j^{th}$ column. Assume $\sum_{1 \leq j \leq n} a_{ij} \leq 1$ for all $1 \leq ...
7
votes
4answers
876 views

How many minors I need to check to conclude all minors will vanish ?

Given a $m \times n$ matrix $n>m$, I was trying to check if all its $m \times m$ minor vanish. I remember hearing that one really does not need to check all possible minors in order to conclude ...
7
votes
4answers
492 views

If the series Σ pᵃ⁽ʷ⁾·xᴵʷᴵ is rational, is Σ a(w)·xᴵʷᴵ also rational (summation over words w in a regular language)?

Let $p$ be a prime number and let $a_i$ be a sequence of natural numbers such that the series $\sum_{i=1}^\infty p^{a_i} x^i$ is rational. A warm-up question: Question 1. Does it follow that the ...
2
votes
0answers
157 views

The orthogonal of $[A,B]$ in $M_n(k)$

Let ${\mathcal A}$ be the algebra spanned by the words in two letters $x$ and $y$. Its (infinite) basis is $1,x,y,x^2,xy,yx,y^2,...$ Let ${\mathcal A}_0$ be the sub-space (warning: not the ...
11
votes
0answers
562 views

Regular languages of matrices and their generating functions

My question is somewhat related to this question. Let us fix natural numbers $k$ and $C$. Let $A$ be an automaton whose alphabet consists of $k\times k$ matrices with integer coefficients of ...
3
votes
3answers
2k views

What's the maximum determinant of the (0, 1) matrix from M(n, R)?

If there's no exact formula what's the nearest upper and lower bounds do you know?
1
vote
0answers
352 views

Minimizing quadratic form over permutations

Let $Q$ be an $n \times n$ real symmetric matrix and $x$ an $n \times 1$ real vector. Consider the following minimization problem: $\min_{\pi \in S_n} ~(\pi x)^{\rm T} Q (\pi x)$, where $S_n$ ...
3
votes
0answers
299 views

Combinatorics of signed oriented graphs/skew-symmetric matrices

Consider a "complete" signed graph on $n$ vertices indexed by $1,2,\dots,n$, that is, a graph in which any two distinct vertices $i$ and $j$ are connected by an oriented edge. For each pair of ...
12
votes
3answers
2k views

Number of invertible {0,1} real matrices?

This question is inspired from here, where it was asked what possible determinants an $n \times n$ matrix with entries in {0,1} can have over $\mathbb{R}$. My question is: how many such matrices ...
12
votes
3answers
2k views

Number of unique determinants for an NxN (0,1)-matrix.

I'm interested in bounds for the number of unique determinants of NxN (0,1)-matrices. Obviously some of these matrices will be singular and therefore won't have a determinant. While it might also be ...
17
votes
2answers
1k views

Lifting matrices mod 2 to integers.

The following question was motivated by my research. Consider a $n\times n$ matrix whose elements are $0$'s or $1$'s such that the determinant is odd. The question is: is it possible to assign signs ...
1
vote
2answers
1k views

Convert a confusion matrix to a distance/covariance matrix

Suppose I have a confusion matrix $A$ for a set of points: entry $i,j$ is the fraction of time over all $j$ (and similarly over all $i$) that when $i$ is present then $j$ is recognized (This means ...
13
votes
3answers
677 views

Orthogonal matrices with small entries

Is it true that for any $n$, there exists a $n \times n$ real orthogonal matrix with all coefficients bounded (in absolute value) by $C/\sqrt{n}$, $C$ being an absolute contant ? Some remarks : If ...