Symmetric matrix as a sum of symmetric matrices

Question

Let matrix $M \in \mathbb{N}^{5 \times 5}$ be symmetric with non-negative integer entries and zeros on the main diagonal and having the property that the row sums are equal to $2r$ for some $r \geq 2$. I want to prove that $M$ can be written as a non-negative integral linear combination of $5 \times 5$ symmetric matrices having non-negative integer entries with zero entries on the main diagonal and having the property that the row sums are equal to $2$. Is there way to prove this?

I tried with some simple examples and it seems to be correct.

Answer 1

IDEA:

The row sums of $M$ are even, so there is either 0 or 2 or 4 odd numbers, and the diagonal entries are all zeros.

So if you have even entries, for example if you have that in $M$ the entries $m_{1,5}=m_{5,1}= 8$ then you will have in your linear combination $4$ multiplied by a matrix having all its entries on these rows are $0$ except $a_{1,5}=a_{5,1}=2$, and so on ...

Also if there is $2$ odd entries, for example $m_{1,5}=m_{5,1}=5$ and $m_{1,4}=m_{4,1}=7$, then in your linear combination you'll have $2$ multiplied by a matrix having $a_{1,5}=a_{5,1}=2$ and all other entries on these rows are zeros, and $3$ multiplied by a matrix having $b_{1,4}=b_{4,1}=2$ and all other entries on these rows are zeros, and a matrix having $c_{1,4}=c_{4,1}=c_{1,5}=c_{5,1}=1$ and all other entries on these rows are zeros, and so on...

I hope you can reach a proof from this hint and I am sorry because I am not able to write the whole proof now.

Answer 2

Yes, this conjecture is correct.

First consider the following matrices.

$X_1=\begin{pmatrix}0&0&1&1&0 \\0&0&1&0&1\\1&1&0&0&0\\1&0&0&0&1\\0&1&0&1&0\\\end{pmatrix}$, $X_2=\begin{pmatrix}0&0&1&0&1 \\0&0&1&1&0\\1&1&0&0&0\\0&1&0&0&1\\1&0&0&1&0\\\end{pmatrix}$, $X_3=\begin{pmatrix}0&0&1&0&1 \\0&0&0&2&0\\1&0&0&0&1\\0&2&0&0&0\\1&0&1&0&0\\\end{pmatrix}.$

If we could subtract one of the $X_i$ from $M$ without making any entry negative, then we would leave a matrix of the same type as $M$ but with $r$ reduced by 1. This process would therefore reduce $M$ to zero as we require.

If all off-diagonal entries of $M$ were non-zero we could subtract $X_1$. So, without loss of generality, we can suppose that $M_{12}=0$.

CASE 1. If no row of $M$ has three or more zeroes.

Without loss of generality we can suppose that $M$ has the following form where $A,B,C,D,E,F$ are all non-zero.

$M=\begin{pmatrix}0&0&A&B&C \\0&0&D&E&F\\A&D&0&.&.\\B&E&.&0&.\\C&F&.&.&0\\\end{pmatrix}$

If any of the dots were non-zero then a matrix like $X_1$ can be subtracted from $M$. Otherwise, all the dots are zero. Then $$A+D=B+E=C+F=2r. (*)$$ However, we would then have the sum of the first two rows equal to $6r$, a contradiction.

CASE 2. If a row of $M$ has four zeroes.

Without loss of generality we can suppose that $M$ has the following form.

$M=\begin{pmatrix}0&0&0&0&2r \\0&0&A&B&0\\0&A&0&C&0\\0&B&C&0&0\\2r&0&0&0&0\\\end{pmatrix}$

Then simple algebra shows that $A=B=C=r$ and $M$ is the sum of $r$ copies of $\frac {1}{r} M$.

CASE 3. If $M$ has three zeroes in a row but that no row has four or more zeroes.

Let $M=\begin{pmatrix}0&0&.&.&. \\0&0&.&.&.\\.&.&0&F&G\\.&.&F&0&H\\.&.&G&H&0\\\end{pmatrix}$

CASE 3(a). If $F=G=H=0$

Then the method used for $(*)$ gives a contradiction.

CASE 3(b). If two of $F,G,H$ are $0$, w.l.g. $F=G=0$

Then either $X_1$ or $X_2$ can be subtracted.

CASE 3(c). If only one of $F,G,H$ is $0$, w.l.g $F=0$.

Since every row has at least two non-zero elements, the possibilities for $M$ are, without loss of generality, as follows, where $+$ indicates a positive element.

$\begin{pmatrix}0&0&+&0&+ \\0&0&0&+&+\\+&0&0&0&G\\0&+&0&0&H\\+&+&G&H&0\\\end{pmatrix}$ and $\begin{pmatrix}0&0&+&.&. \\0&0&+&.&.\\+&+&0&0&G\\.&.&0&0&H\\.&.&G&H&0\\\end{pmatrix}$

Considering row totals for Rows 3 and 4 of the LH matrix shows that $M_{42}>1$ and so $X_3$ can be subtracted. For the RH matrix, one of $X_1, X_2$ can be subtracted unless the matrix is $\begin{pmatrix}0&0&+&+&0 \\0&0&+&+&0\\+&+&0&0&G\\+&+&0&0&H\\0&0&G&H&0\\\end{pmatrix}$

Then the sum of elements in Rows 1 and 2 must equal the sum of elements in Rows 3 and 4. Therefore $G=H=0$, a contradiction.

CASE 3(d). If $F,G,H$ are all non-zero.

Then a matrix like either $X_1$ or $X_2$ can be subtracted since the top two rows contain at least 4 non-zero elements.

Answer 3

A graph theoretic proof

Consider $M$ to be the adjacency matrix for a graph $G$. Then $G$ is a graph with no loops and 5 vertices, each of degree $2r$. We are required to prove that:

$G$ contains one or more simple cycles (i.e. containing no repeated vertex) which include every point precisely once.

Since all vertices have even degree, each component of $G$ must have an Eulerian cycle and therefore each vertex of $G$ is in a simple cycle and at least one of these simple cycles has length at least 3.

We can suppose every vertex of $G$ is joined to more than one vertex.

Suppose on the contrary that vertex 1 was only joined to vertex 2. By the equality of degrees, vertices 1 and 2 then form a component of $G$. The points 3,4,5 of the other component must then be joined in pairs and $G$ has simple cycles (1,2) and (3,4,5).

We can suppose $G$ only has simple cycles of lengths 2 and 3

There is nothing to prove if $G$ has a simple cycle of length 5, so suppose $G$ has the cycle (1,2,3,4). If vertex 5 were connected to two adjacent points in this cycle, say vertices 1 and 2, then (1,5,2,3,4) would be a simple cycle. So we can suppose 5 is only joined to, say, 1 and 3. Then (1,5,3,4) and ((1,2,3,5) are cycles and so 2 and 4 are also only joined to 1 and 3. There are then $6r$ edges from vertices 2,4,5 to 1 and 3, contradicting the degrees of 1 and 3.

Now consider a cycle of length 3, say (1,2,3). If vertex 4 were joined to two of these points then we would have a cycle of length 4. So vertex 4 is joined to vertex 5 and, say, vertex 1. Vertex 5 also has to be joined to precisely one of 1,2,3. This must be the same vertex 1, otherwise we would obtain a simple cycle of length 5. Vertices 4 and 5 can only be joined by $1$ edge (and similarly vertices 2 and 3 are only joined by $1$ edge) otherwise we would have simple cycles (1,2,3) and (4,5). Therefore there are $4(2r-1)$ edges from vertices 2,3,4,5 to vertex 1. Then $8r-4=2r$, which is impossible.

Answer 4

This is my take on the graph theoretic approach by S. Dolan. Credits go to him.

---

Let $M$ be the adjacency matrix of a graph $G$, so that $G$ is a graph on $5$ vertices with no loops and such that each vertex has degree $2r$.

Claim: It is enough to prove that $G$ contains a collection of simple cycles such that each vertex belongs to exactly one of these cycles.

Indeed, if $H$ is the $G$-subgraph that corresponds to this collection, then each vertex of $H$ has degree exactly $2$. We can thus take the adjacency matrix of $H$ as one of the matrices in our integral linear combination that adds up to $M$.

We are hence left with the same problem, except now the rows of $M$ add up to $2(r-1)$; equivalently, except the vertices of $G$ have degree $2(r-1)$. Induction then takes care of finding the other matrices in our integral linear combination.

---

Let $v_1,v_2,v_3,v_4$ and $v_5$ be the vertices of $G$. We will prove the claim by studying different cases.

Case $(1)$: $G$ has a vertex which is joined to only one other vertex.

Assume without loss of generality that $v_1$ is joined only to $v_2$. Since all vertices have equal degrees, $v_2$ must also be joined only to $v_1$.

This implies that if some $u$ in $\{v_3, v_4,v_5\}$ were also joined to only one other vertex $w$, we would have $w \in \{v_3, v_4,v_5\}\setminus\{u\}$. Equality of degrees would then require that the remaining vertex be joined to itself, in contradiction to $G$ having no loops. It follows that each of $\{v_3, v_4,v_5\}$ is connected to the other two.

The collection of simple cycles $\{(v_1,v_2), (v_3,v_4,v_5)\}$ satisfies the claim and handles this case.

---

Case $(2)$: Each vertex of $G$ is joined to at least two other vertices.

By Veblen's Theorem, $G$ can be written as the union of disjoint simple cycles. We break down into subcases.

---

$\qquad (2.1)$: $G$ has a simple cycle of length $5$.

In this case, the claim is obviously satisfied and there is nothing to prove.

---

$\qquad (2.2)$: $G$ has a simple cycle of length $4$.

Let $(v_1,v_2,v_3,v_4)$ be the simple cycle.

---

$\qquad\qquad(2.2.1)$: $v_5$ is joined to two vertices that are adjacent in the cycle.

If that were the case, then we could enlarge the simple cycle to have length $5$. This reduces the problem to case $(2.1)$, which we have already handled.

---

$\qquad\qquad(2.2.2)$: No two vertices adjacent in the cycle are both joined to $v_5$.

Without loss of generality, suppose $v_5$ were joined to vertices $v_1$ and $v_3$. Notice that $v_5$ cannot be joined to any other vertex.

If $v_2$ and $v_4$ weree joined, then we could take the simple cycle $(v_1,v_2,v_4,v_3,v_5)$, handled by case $(2.1)$.

If $v_2$ and $v_4$ were not joined, then each of $\{v_2, v_4,v_5\}$ would be joined only to $v_1$ and $v_3$. This would contradict each vertex having equal degree, and finishes this case.

---

$\qquad (2.3)$: $G$ has a simple cycle of length $3$.

Let $(v_1,v_2,v_3)$ be the simple cycle.

---

$\qquad\qquad(2.3.1)$: One of $\{v_4, v_5\}$ is joined to two vertices in the cycle.

If that were the case, then we could enlarge the simple cycle to have length $4$. This reduces the problem to case $(2.2)$, which we have already handled.

---

$\qquad\qquad(2.3.1)$: No two vertices in the cycle are both joined to one of $\{v_4, v_5\}$.

Without loss of generality, suppose $v_4$ were joined to vertices $v_1$ and $v_5$. Notice that $v_4$ cannot be joined to any other vertex.

If $v_5$ were joined to one of $\{v_2,v_3\}$, then we could enlarge the simple cycle to have length $5$, handled by case $(2.1)$. Indeed, if $v_5$ were joined to $v_2$ we would have the cycle $(v_1,v_3, v_2,v_5,v_4)$ and if $v_5$ were joined to $v_3$ we would have the cycle $(v_1,v_2,v_3,v_5,v_4)$.

Suppose instead that $v_5$ were joined only to $v_1$ and $v_4$.
If there were more than edge joining $v_4$ and $v_5$, the collection $\{(v_1,v_2,v_3),(v_4,v_5)\}$ satisfies the claim.
If there were more than edge joining $v_2$ and $v_3$, the collection $\{(v_1,v_4,v_5),(v_2,v_3)\}$ satisfies the claim.
If $v_4$ were joined to $v_5$ by a single edge and $v_2$ were also joined to $v_3$ by a single edge, then $v_1$ would have degree $4(2r - 1) > 2r$, which contradicts our hypotheses and concludes this case.

---

$\qquad (2.4)$: $G$ has no simple cycle of length $3$ or more.

We show that this case is impossible.

$G$ does not have loops, so in this case it would contain only cycles of length $2$. $G$ would then be bipartite: its vertices could be divided into two disjoint sets $U$ and $V$ such that every edge of $G$ joins a vertex in $U$ to a vertex in $V$. But $G$ has $5r$ edges and one of $\{U, V\}$ has at most two vertices. This contradicts each vertex having degree $2r$ and finishes the last case.