# Symmetric matrix as a sum of symmetric matrices

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.

• I need to prove that any $M$ (with the property listed) can be written as a non-negative integral linear combination of matrices with the property listed. $m$ is not specific here. – jack Sep 21 at 9:28
• I imagine this result is true for all dimensions, not just 5. – S. Dolan Sep 21 at 17:00

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.

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.

• With hindsight, CASE 1 can be subsumed into CASE 3(a) to shorten this proof a little. – S. Dolan Sep 21 at 16:41

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.

• I don't think I follow your 'We are required to prove that'. Perhaps you meant something like: $G$ contains a collection of simple cycles such that each vertex belongs to exactly one of these cycles. Is that right? – Fimpellizieri Sep 22 at 21:04
• Yes, that is correct. – S. Dolan Sep 22 at 21:06
• I think your answer would benefit from better writing. I think you are trying to handle cases here rather than actually going 'without loss of generality' and it makes parsing the answer confusing. $G$ can very trivially have a simple cycle of length $5$, but I guess you're dismissing it as the easiest case for which what we need to prove is basically handed to us on a platter. – Fimpellizieri Sep 22 at 21:18
• If G has a simple cycle of length 5 then, by definition, G contains a simple cycle which include every point precisely once. – S. Dolan Sep 22 at 21:24
• Yes, that is my point. It's not 'Without loss of generality, we can suppose $G$ has no simple cycle of length $5$' and it most definitely isn't 'By definition, $G$ has no simple cycle of length $5$'. It's just that when $G$ has a simple cycle of length $5$, there is nothing to prove, so this case is done. Your answer is tackling cases, but is structured and written as something else, which makes it harder to parse. – Fimpellizieri Sep 22 at 21:28

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.