4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – jack
    Sep 21, 2019 at 9:28
  • $\begingroup$ I imagine this result is true for all dimensions, not just 5. $\endgroup$
    – user502266
    Sep 21, 2019 at 17:00

4 Answers 4

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ With hindsight, CASE 1 can be subsumed into CASE 3(a) to shorten this proof a little. $\endgroup$
    – user502266
    Sep 21, 2019 at 16:41
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$ Sep 22, 2019 at 21:04
  • $\begingroup$ Yes, that is correct. $\endgroup$
    – user502266
    Sep 22, 2019 at 21:06
  • $\begingroup$ 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. $\endgroup$ Sep 22, 2019 at 21:18
  • $\begingroup$ If G has a simple cycle of length 5 then, by definition, G contains a simple cycle which include every point precisely once. $\endgroup$
    – user502266
    Sep 22, 2019 at 21:24
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 22, 2019 at 21:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .