{"id":2160,"date":"2017-02-07T12:05:29","date_gmt":"2017-02-07T17:05:29","guid":{"rendered":"http:\/\/matroidunion.org\/?p=2160"},"modified":"2017-02-07T12:24:54","modified_gmt":"2017-02-07T17:24:54","slug":"the-lights-out-game","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=2160","title":{"rendered":"The Lights Out Game"},"content":{"rendered":"

In this short post, I will discuss a cute graph theory problem called the\u00a0Lights Out Game.<\/em>\u00a0The set-up is as follows. \u00a0We are given a graph $G=(V,E)$, where we consider each vertex as a\u00a0light<\/em>. \u00a0At the beginning of the game, some subset of the vertices are ON, and the rest of the vertices are OFF. \u00a0We are allowed to\u00a0press<\/em> any vertex $v$, which has the effect of switching\u00a0the state of $v$ and all of the neighbours of $v$. \u00a0The goal is to determine if it is possible to press some sequence of vertices to turn off all the lights.<\/p>\n

The version of this\u00a0game where $G$ is the $5 \\times 5$ grid was produced in the real world by Tiger Electronics, and has a bit of a cult following. \u00a0For example, there is a dedicated\u00a0wikipedia page<\/a>\u00a0and this\u00a0site<\/a>\u00a0(from which I borrowed the image below)\u00a0even has the original user manuals.<\/p>\n

\"\"<\/a><\/p>\n

The goal of this post is to prove the following theorem.<\/p>\n

Theorem.<\/strong> Let $G=(V,E)$ be a graph for which all the lights are initially ON. \u00a0Then it is always possible to press a sequence of vertices to switch all the lights OFF.<\/p>\n

(Note that if not all the lights are ON initially, it will not always be possible to switch all the lights OFF. \u00a0For example, consider just a single edge\u00a0where only one light is ON initially.)<\/p>\n

Proof.\u00a0<\/strong>Evidently, there is no point in pressing a vertex more than once, and the sequence in which we press vertices does not matter. \u00a0Thus, we are searching for a subset $S$ of vertices such that $|S \\cap N[v]|$ is odd for all $v \\in V$, where $N[v]$ is the closed neighbourhood of $v$<\/em>\u00a0(the neighbours of $v$ together with $v$ itself). \u00a0We can encode the existence of such a set $S$ by doing linear algebra over the binary field $\\mathbb{F}_2$.<\/p>\n

Let $A$ be the $V \\times V$ adjacency matrix of $G$, and let $B=A+I$. Note that the\u00a0column corresponding to a vertex $v$ is the characteristic vector of the closed neighbourhood of $v$. Thus, the required set $S$ exists if and only if the all ones vector $\\mathbb{1}$ is in the column\u00a0space of $B$. \u00a0Since $B$ is symmetric, this is true if and only if\u00a0$\\mathbb{1}$ is in the row space of $B$. \u00a0Let $B^+$ be the matrix obtained from $B$ by adjoining $\\mathbb{1}$ as an additional row. Thus, we can turn all the lights OFF\u00a0if and only if $B$ and $B^+$ have the same rank.<\/p>\n

Since this is a matroid blog, let $M(B)$ and $M(B^+)$ be the column matroids of $B$ and $B^+$ (over $\\mathbb{F}_2$). We will prove the stronger result that\u00a0$M(B)$ and $M(B^+)$ are actually the same matroid. Every circuit of\u00a0$M(B^+)$ is clearly a dependent set in\u00a0$M(B)$. \u00a0On the other hand let $C \\subseteq V$ be a circuit of\u00a0$M(B)$. \u00a0Then $\\sum_{v \\in C} \\chi(N[v])=\\mathbb{0}$, where $\\chi(N[v])$ is the characteristic vector of the closed neighbourhood of $v$. Therefore, in the subgraph of $G$ induced by the vertices in $C$, each vertex has odd degree. \u00a0By the Handshaking Lemma, it follows that $|C|$ is even, and so $C$ is also dependent in\u00a0$M(B^+)$.<\/p>\n

Reference<\/strong><\/p>\n

Anderson, M., & Feil, T. (1998). Turning lights out with linear algebra. Mathematics Magazine<\/i>, 71<\/i>(4), 300-303.<\/p>\n","protected":false},"excerpt":{"rendered":"

In this short post, I will discuss a cute graph theory problem called the\u00a0Lights Out Game.\u00a0The set-up is as follows. \u00a0We are given a graph $G=(V,E)$, where we consider each vertex as a\u00a0light. \u00a0At the beginning of the game, some … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":10,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-2160","post","type-post","status-publish","format-standard","hentry","category-matroids"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/2160","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/users\/10"}],"replies":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2160"}],"version-history":[{"count":19,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/2160\/revisions"}],"predecessor-version":[{"id":2180,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/2160\/revisions\/2180"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2160"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2160"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2160"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}