## SOLUSI PERMAINANAN LIGHT OUT MENGGUNAKAN ALJABAR LINIER

## Akhmad Basuki, Thresye, Pardi Affandi
Program Studi Matematika Fakultas MIPA Universitas Lambung Mangkurat Jln. A. Yani KM. 36, Banjarbaru, 70714, Kalimantan Selatan Email: akhmadbasuki1@gmail.com

## ABSTRAK
Sistem persamaan linier dapat diterapkan untuk mencari dan menyelidiki solusi dari permainan light out yang berukuran 3 × 3, 4 × 4 dan 5 × 5 . Dimana Permainan light out tersebut dibentuk kedalam sistem persamaan 𝑨𝑨𝑨𝑨 = 𝒃𝒃 dan dicari solusinya  dengan menggunakan metode eliminasi  Gauss Jordan. Tujuan penelitian ini adalah untuk menentukan permainan tersebut punya solusi atau tidak dan mencari  solusi  optimalnya. Penelitian ini dilakukan dengan cara studi literatur. Hasil dari penelitiannya adalah permainan light out yang berukuran 3 × 3 memiliki solusi tunggal untuk setiap kondisi permainan dan sedangkan permainan light out yang berukuran 4 × 4 dan 5 × 5 memiliki solusi untuk kondisi tertentu dan solusi yang dihasilkan tidak tunggal.
Kata Kunci : Persamaan Linier, Permainan Light Out, Eliminasi Gauss Jordan

## ABSTRACT
Linear system can using for search and looking for solution of light out game which form 3 × 3, 4 × 4 dan 5 × 5 . This game can be belong to system linear 𝑨𝑨𝑨𝑨 = 𝒃𝒃 and can be searched with using Gauss Jordan elemenation. The purpose of this research is to get this game have a solution or not and search optimal solution. The method of this research is literature study. The result of this research are for light out game which form 3 × 3 have a unique solution for every configuration, for light out game which form 4 × 4 and 5 × 5 have a solution for certain conditions  and have a not unique solution .
Keywords : Linear equation, Light Out Game, Gauss Jordan elemenation.

## 1. PENDAHULUAN
Persamaan linier adalah sebuah persamaan aljabar yang tiap sukunya mengandung konstanta atau perkalian konstanta dengan variabel tunggal. Suatu persamaan linier dari 𝑚𝑚 persamaan dalam 𝑛𝑛 peubah (variabel) akan membentuk sistem persamaan linier. Dimana dalam sistem persamaan linier ada yang tidak mempunyai solusi, mempunyai solusi tunggal, atau mempunyai tak hingga solusi. Sistem persamaan linier dapat berfungsi untuk menyelesaikan beberapa permasalahan dalam kehidupan nyata. Beberapa permasalahan dalam kehidupan sehari-hari dapat dibentuk dalam sistem persamaan linier dan kemudian diselesaikan dengan cara mencari solusinya.  Sistem persamaan linier ini dapat diterapkan untuk mencari dan menyelidiki solusi dari permainan light out [1]. Berdasarkan penjelasan di atas maka penulis tertarik untuk mengkaji kembali tulisan Anderson 1998.

## 2. TINJAUAN PUSTAKA

## 2.1 Sistem Persamaan Linier dan Matriks
Suatu persamaan linear dalam 𝑛𝑛 peubah (variabel) adalah persamaan dengan bentuk
𝑎𝑎 1 𝑥𝑥 1 + 𝑎𝑎 2 𝑥𝑥 2 + ⋯ + 𝑎𝑎 𝑛𝑛 𝑥𝑥 𝑛𝑛 = 𝑏𝑏
dimana 𝑎𝑎 1 , 𝑎𝑎 2 , . . . . 𝑎𝑎 𝑛𝑛 dan 𝑏𝑏 adalah bilangan-bilangan real dan 𝑥𝑥 1 , 𝑥𝑥 2 , 𝑥𝑥 3 , ⋯ 𝑥𝑥 𝑛𝑛 adalah variabel. Dengan demikian maka suatu sistem linear dari 𝑚𝑚 persamaan dalam 𝑛𝑛 peubah adalah satu sistem berbentuk:
𝑎𝑎 11 𝑥𝑥 1 + 𝑎𝑎 12 𝑥𝑥 2 + ⋯ + 𝑎𝑎 1𝑛𝑛 𝑥𝑥 𝑛𝑛 = 𝑏𝑏 1
𝑎𝑎 21 𝑥𝑥 1 + 𝑎𝑎 22 𝑥𝑥 2 + ⋯ + 𝑎𝑎 2𝑛𝑛 𝑥𝑥 𝑛𝑛 = 𝑏𝑏 2 ⋮ 𝑎𝑎 𝑚𝑚1 𝑥𝑥 1 + 𝑎𝑎 𝑚𝑚2 𝑥𝑥 2 + ⋯ + 𝑎𝑎 𝑚𝑚𝑛𝑛 𝑥𝑥 𝑛𝑛 = 𝑏𝑏 𝑚𝑚 dimana 𝑎𝑎 𝑖𝑖𝑖𝑖 dan 𝑏𝑏 𝑖𝑖 adalah elemen bilangan real. Sistem ini disebut sistem linear 𝑚𝑚 × 𝑛𝑛 . Jadi sistem persamaan Linear adalah sebuah himpunan berhingga dari persamaan- persamaan linier dalam peubah 𝑥𝑥 1 , 𝑥𝑥 2 , … , 𝑥𝑥 𝑛𝑛 . [2] 2.2 Ruang Vektor
Jika  ditinjau 𝑹𝑹 𝒏𝒏 sebagai himpunan semua matriks 𝑛𝑛 × 1 dengan entri-entri bilangan real. Penjumlahan dan perkalian skalar  untuk vektor vektor dalam 𝑹𝑹 𝒏𝒏 tak lain adalah penjumlahan dan perkalian skalar yang biasa dari matriks. Lebih umum, misalkan 𝑹𝑹 𝒎𝒎 × 𝒏𝒏 menyatakan himpunan semua matriks 𝑚𝑚 × 𝑛𝑛 dengan entri-entri bilangan real. Jika 𝑨𝑨 = ( 𝒂𝒂 𝒊𝒊𝒊𝒊 ) dan 𝑩𝑩 = �𝒃𝒃 𝒊𝒊𝒊𝒊 � maka jumlah 𝑨𝑨 + 𝑩𝑩 didefinisikan sebagai matriks 𝑪𝑪 = ( 𝒄𝒄 𝒊𝒊𝒊𝒊 ) yang berorde 𝑚𝑚 × 𝑛𝑛 , di mana 𝒄𝒄 𝒊𝒊𝒊𝒊 = 𝒂𝒂 𝒊𝒊𝒊𝒊 + 𝒃𝒃 𝒊𝒊𝒊𝒊 . Jika diberikan skalar ∝ , maka dapat didefinisikan ∝ 𝑨𝑨 sebagai matriks 𝑚𝑚 × 𝑛𝑛 dimana entri ke- 𝑖𝑖𝑖𝑖 adalah ∝ 𝒂𝒂 𝒊𝒊𝒊𝒊 . Jadi, dengan mendefinisikan operasi-operasi pada himpunan 𝑹𝑹 𝒎𝒎 × 𝒏𝒏 , telah membentuk suatu sistem matematika. Operasi-operasi penjumlahan dan perkalian skalar pada 𝑹𝑹 𝒎𝒎 × 𝒏𝒏 mengikuti aturan-aturan ilmu hitung tertentu dan membentuk aksioma-aksioma yang digunakan untuk mendefinisikan ruang vektor.[3]
2.3 Permainan Light Out
Pada tahun 1970-an  Parkers Brother merilis sebuah permainan puzzle yang bernama Merlin dengan ukuran 3 × 3 . Kemudian pada tahun 1995 sebuah perusahaan permainan elektronik mengembangkan permainan tersebut dan permainan tersebut diberi  nama light out , dimana ukuran permainannya di perbesar. Light Out adalah permainan puzzle yang terdiri atas 25 tombol yang tersusun atas 5 baris dan 5 kolom. Setiap tombol kondisinya menyala atau mati. Ketika permainan dimulai akan ada lampu yang menyala atau mati secara acak. Tombol yang menyala ketika ditekan akan mati dan begitu juga sebaliknya, tombol yang ditekan juga akan mempengaruhi kondisi lampu bagian vertikal dan horizontal didekatnya atau tetangganya (tetangga bagian diagonal tidak berpengaruh). Permainan ini akan dimenangkan ketika semua lampu mati. [4]
Pada pengamatan pertama pada permainan light out bahwa penekanan dua kali sama artinya dengan tidak menekan tombol sama sekali. Karena penekanan tombol dua kali akan menyebabkan permainan kembali ke kondisi semula. Oleh karena itu untuk setiap kondisi awal saat permainan dimulai strategi yang perlu dibutuhkan adalah mencari tombol mana saja yang harus ditekan dengan syarat hanya satu kali penekanan. [4]
Pada pengamatan yang kedua menunjukkan bahwa penekanan tombol hanya tergantung pada banyak tombol yang ditekan tidak pada urutan. Ini menunjukkan bahwa urutan penekanan tombol bersifat komutatif.
Pada permainan ini ada dua kondisi lampu yaitu nyala atau mati, dalam hal ini kondisi lampu akan direpresentasikan dalam modulo 2 dimana diasumsikan satu untuk kondisi lampu menyala dan nol untuk kondisi lampu mati. [2]
Pada permainan light out ukuran 𝑛𝑛 × 𝑛𝑛 , kondisi 𝑛𝑛 2 tombol dapat dituliskan dalam sebuah vektor berikut
𝒃𝒃 = ( 𝑏𝑏 1 , 𝑏𝑏 2 , 𝑏𝑏 3 , ⋯ , 𝑏𝑏 𝑛𝑛 2 ) P T
dimana 𝑏𝑏 1 , 𝑏𝑏 2 , 𝑏𝑏 3 , ⋯ , 𝑏𝑏 𝑛𝑛 2 merepresentasikan kondisi awal saat permainan dimulai. Setiap kondisi awal dari 𝒃𝒃 akan dicari tombol mana saja yang akan ditekan, dimana akan dinotasikan sebagai
𝑨𝑨 = ( 𝑥𝑥 1 , 𝑥𝑥 2 , 𝑥𝑥 3 , ⋯ , 𝑥𝑥 𝑛𝑛 2 ) P T
dimana 𝑥𝑥 1 , 𝑥𝑥 2 , 𝑥𝑥 3 , ⋯ , 𝑥𝑥 𝑛𝑛 2 representasi tombol yang akan ditekan dalam permainan.[1] Secara umum, diberikan konfigurasi 𝒃𝒃 = �𝑏𝑏 𝑖𝑖 , 𝑖𝑖 � , solusi penyelesain permainan tersebut dapat dirumuskan dalam sebuah sistem persamaan linier yaitu solusi penyelesain permainan tersebut dapat dirumuskan dalam sebuah sistem persamaan linier yaitu
∑ 𝑨𝑨 𝒊𝒊 , 𝒊𝒊 𝑨𝑨 𝒊𝒊 , 𝒊𝒊 = 𝒃𝒃 𝒊𝒊 , 𝒊𝒊
𝟏𝟏≤𝒊𝒊≤𝒏𝒏 𝟏𝟏≤𝒊𝒊≤𝒏𝒏
dimana 𝑥𝑥 𝑖𝑖 , 𝑖𝑖 ∈ {0,1} , 𝑥𝑥 𝑖𝑖 , 𝑖𝑖 merepresentasikan tombol mana saja yang harus ditekan, dan 𝑥𝑥 𝑖𝑖 , 𝑖𝑖 dinamakan matriks strategi dan 𝑏𝑏 𝑖𝑖 , 𝑖𝑖 merepresentasikan kondisi lampu atau tombol pada awal permainan. [5]

## 3. METODE PENELITIAN
Penelitian ini dilakukan dengan cara mengumpulkan referensi pendukung yang berkaitan dengan persamaan linier dan solusi permainan light out. Referensi tersebut dipelajari, dibahas serta dijabarkan sehingga diperoleh solusi dari permainan tersebut. Langkah pada pembahasan meliputi
a. Light Out ukuran 𝟑𝟑 × 𝟑𝟑
b. Light Out ukuran 4x4 dan 5x5

## 4. HASIL DAN PEMBAHASAN
Pada  saat memulai permainan light out yang berukuran 𝑛𝑛 × 𝑛𝑛 , dimana ada sebanyak 𝑛𝑛 2 jumlah tombol, setiap tombol kemungkinannya menyala atau padam. Untuk tombol yang menyala ketika ditekan akan menjadi padam begitu juga sebaliknya. Penekanan tombol juga mempengaruhi kondisi samping vertikal dan horizontal dari tombol tersebut, bagian samping vertikal dan horizontal yang sebelumnya menyala akan menjadi padam dan begitu juga sebaliknya.
Permainan ini akan dimenangkan ketika semua lampu menjadi padam. Strategi permainan ini adalah mencari tombol mana saja yang harus ditekan untuk menghasilkan solusi yang optimal (penekanan tombol sedikit mungkin).
4.1 Light Out ukuran 𝟑𝟑 × 𝟑𝟑
Pada permainan ini ada dua kondisi lampu yaitu nyala atau mati, dalam hal ini kondisi lampu akan direpresentasikan dalam modulo 2 dimana diasumsikan satu untuk kondisi lampu menyala dan nol untuk kondisi lampu mati
Gambar 4.1.1 ( 𝑥𝑥 1 , 𝑥𝑥 2 , ⋯ , 𝑥𝑥 9 ) merepresentasikan tombol-tombol permainan light out ukuran 3 × 3 dan ( 𝑏𝑏 1 , 𝑏𝑏 2 , ⋯ , 𝑏𝑏 9 ) merepresentasikan kondisi tombol pada awal permainan
Pada permainan light out ukuran 3 × 3 , kondisi 9 tombol dapat dituliskan dalam sebuah vektor berikut
𝒃𝒃 = ( 𝑏𝑏 1 , 𝑏𝑏 2 , 𝑏𝑏 3 , ⋯ , 𝑏𝑏 8 , 𝑏𝑏 9 ) P T
dimana 𝑏𝑏 1 , 𝑏𝑏 2 , 𝑏𝑏 3 , ⋯ , 𝑏𝑏 8 , 𝑏𝑏 9 merepresentasikan kondisi awal saat permainan dimulai. Setiap kondisi awal dari 𝒃𝒃 akan dicari tombol mana saja yang akan ditekan, dimana akan dinotasikan sebagai
𝑨𝑨 = ( 𝑥𝑥 1 , 𝑥𝑥 2 , 𝑥𝑥 3 , ⋯ , 𝑥𝑥 8 , 𝑥𝑥 9 ) P T
dimana 𝑥𝑥 1 , 𝑥𝑥 2 , 𝑥𝑥 3 , ⋯ , 𝑥𝑥 8 , 𝑥𝑥 9 representasi tombol yang akan  ditekan dalam permainan. Jika permainan dimulai dengan kondisi awal 𝒃𝒃 dicari dengan strategi 𝑥𝑥⃗ , maka ketika dimainkan 𝑥𝑥 1 , lampu 𝑏𝑏 1 menjadi 𝑏𝑏 1 + 𝑥𝑥 1 . Untuk membuat 𝑏𝑏 1 menjadi nol maka perlu memainkan 𝑥𝑥 2 dan 𝑥𝑥 4 juga. Oleh karena itu 𝑏𝑏 1 + 𝑥𝑥 1 + 𝑥𝑥 2 + 𝑥𝑥 4 = 0  dan  didapat persamaan
𝑥𝑥 1 + 𝑥𝑥 2 + 𝑥𝑥 4 = 𝑏𝑏 1
Untuk membuat 𝑏𝑏 2 menjadi nol maka perlu memainkan 𝑥𝑥 1 , 𝑥𝑥 2 , 𝑥𝑥 3 dan 𝑥𝑥 5 . Oleh karena itu didapat persamaan
𝑥𝑥 1 + 𝑥𝑥 2 + 𝑥𝑥 3 + 𝑥𝑥 5 = 𝑏𝑏 2 Dengan cara sama, didapatkan 7 persamaan lainnya. 𝑥𝑥 2 + 𝑥𝑥 3 + 𝑥𝑥 6 = 𝑏𝑏 3 𝑥𝑥 1 + 𝑥𝑥 5 + 𝑥𝑥 7 + 𝑥𝑥 4 = 𝑏𝑏 4 𝑥𝑥 2 + 𝑥𝑥 4 + 𝑥𝑥 6 + 𝑥𝑥 8 + 𝑥𝑥 5 = 𝑏𝑏 5 𝑥𝑥 3 + 𝑥𝑥 5 + 𝑥𝑥 9 + 𝑥𝑥 6 = 𝑏𝑏 6 𝑥𝑥 4 + 𝑥𝑥 8 + 𝑥𝑥 7 = 𝑏𝑏 7 𝑥𝑥 5 + 𝑥𝑥 7 + 𝑥𝑥 9 + 𝑥𝑥 8 = 𝑏𝑏 8 𝑥𝑥 6 + 𝑥𝑥 8 + 𝑥𝑥 9 = 𝑏𝑏 9 Penulisan sistem persamaan linier diatas dapat singkat dengan 𝑨𝑨𝑨𝑨 = 𝒃𝒃 , dimana A adalah matrik ukuran 9 × 9
𝑥𝑥 1 𝑥𝑥 2 𝑥𝑥 3 𝑥𝑥 4 𝑥𝑥 5 𝑥𝑥 6 𝑥𝑥 7 𝑥𝑥 8 𝑥𝑥 9 𝑏𝑏 1 𝑏𝑏 2 𝑏𝑏 3 𝑏𝑏 4 𝑏𝑏 5 𝑏𝑏 6 𝑏𝑏 7 𝑏𝑏 8 𝑏𝑏 9
𝑨𝑨 = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 1 1 0 1 1 1 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 1 1 1 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 1 0 0 1 1 1 0 1 1 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤
Untuk mencari solusi dari matriks 𝑨𝑨 dapat menggunakan operasi-operasi baris dan menerapkan operasi-operasi serempak pada 𝐼𝐼 untuk menghasilkan 𝐴𝐴 −1 atau matriks elementernya. untuk melihat solusi dari matriks tersebut, dengan menggunakan matriks yang diperbesar yaitu menjadi matriks ( 𝐴𝐴 | 𝐼𝐼 ) , matriks tersebut kemudian direduksi menggunakan operasi baris yang sama sehingga matriks 𝐴𝐴 menjadi eselon baris tereduksi atau identitas sedangkan matriks 𝐼𝐼 nanti akan menjadi invers matriks 𝐴𝐴 atau ( 𝐼𝐼 | 𝐴𝐴 −1 ) .
𝐴𝐴 −1 = ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ 1 0 1 0 0 0 1 0 1
0 0 1 0 1 0 1 0 0 1 1 0 1 1 1 0 1 1 0 0 1 0 1 0 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 0 1 1 1 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 1 0 1 ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞
Karena matriks 𝑨𝑨 memiliki invers maka berdasarkan teorema penyelesaian dari sistem 𝑨𝑨𝑨𝑨 = 𝒃𝒃 memiliki tunggal solusi yang yaitu 𝑨𝑨 = 𝑨𝑨 −𝟏𝟏 𝒃𝒃 . 4.2
Light Out ukuran 4x4 dan 5x5
Untuk matriks 4x4 didapat matriks A
𝐴𝐴 = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤
Untuk light out ukuran 5x5 didapat matriks A
𝑨𝑨 = ⎣ ⎢ ⎢ ⎢ ⎡ 𝒁𝒁 𝑰𝑰 𝑶𝑶 𝑶𝑶 𝑶𝑶 𝑰𝑰 𝒁𝒁 𝑰𝑰 𝑶𝑶 𝑶𝑶 𝑶𝑶 𝑶𝑶 𝑶𝑶 𝑰𝑰 𝑶𝑶 𝑶𝑶 𝒁𝒁 𝑰𝑰 𝑶𝑶 𝑰𝑰 𝒁𝒁 𝑰𝑰 𝑶𝑶 𝑰𝑰 𝒁𝒁⎦ ⎥ ⎥ ⎥ ⎤
Dimana 𝑰𝑰 adalah matriks identitas berukuran 5 × 5 , 𝑶𝑶 adalah matriks nol berukuran 5 × 5 dan 𝒁𝒁 adalah matriks
𝒁𝒁 = ⎣ ⎢ ⎢ ⎢ ⎡ 1 1 0 0 0 1 1 1 0 0 0 0 0 1 0 0 1 1 0 1 1 1 0 1 1 ⎦ ⎥ ⎥ ⎥ ⎤
Untuk mencari solusi dari matriks 𝑨𝑨 dapat menggunakan operasi-operasi baris dan menerapkan operasi-operasi serempak pada 𝐼𝐼 untuk menghasilkan 𝐴𝐴 −1 atau matriks elementernya. Untuk melihat solusi dari matriks tersebut, dengan menggunakan matriks yang diperbesar yaitu menjadi matriks ( 𝐴𝐴 | 𝐼𝐼 ) , matriks tersebut kemudian direduksi menggunakan operasi baris sehingga matriks 𝐴𝐴 menjadi eselon baris tereduksi sedangkan matriks 𝐼𝐼 nanti akan menjadi matriks elementer.
( 𝐺𝐺 | 𝑅𝑅 ) = ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 � � � � � 1 1 0 0 1 0 1 0 0 1 1 1 0 0 0 0
1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 1 1 1 1 0 0 0 1 0 1 1 0 0 0 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 0 0 0 0 1 1 1 1 0 1 0 1 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 0 0 1 0 1 1 1 0 0 0 0 1 1 1 0 0 1 0
1 1 1 0 0 1 0 1 0 0 1 1 0 0 0 1 ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞
Untuk menentukan sistem diatas memiliki solusi atau tidak dan untuk menentukan solusi optimal dari sistem tersebut  maka harus digunakan beberapa teorema untuk menyilidiki sistem tersebut memiliki solusi atau tidak.
Teorema 4.2.1
Sistem persamaan 𝑨𝑨𝑨𝑨 = 𝒃𝒃 memiliki solusi jika dan hanya jika 𝒃𝒃 orthogonal dengan dua vektor 𝒏𝒏 𝟏𝟏 dan 𝒏𝒏 𝟐𝟐 , dimana 𝒏𝒏 𝟏𝟏 dan 𝒏𝒏 𝟐𝟐 adalah elemen pada kolom ke-15 dan ke-16 pada matriks 𝐴𝐴 yang telah dibentuk kedalam eselon baris tereduksi. dimana diambil 𝑥𝑥 15 = 0 , 𝑥𝑥 16 = 1 atau 𝑥𝑥 15 = 1 , 𝑥𝑥 16 = 0. 𝒏𝒏 𝟏𝟏 = (1,0,1,1,1,0,0,0,0,1,1,1,0,0,1,0) 𝒏𝒏 𝟐𝟐 = (1,1,1,0,0,1,0,1,0,0,1,1,0,0,0,1)
Bukti: Berdasarkan 𝑨𝑨𝑨𝑨 = 𝒃𝒃 dapat diselesaikan jika dan hanya jika 𝒃𝒃 termuat dalam ruang kolom 𝑨𝑨 , dinotasikan dengan Col ( A ).
Karena 𝑨𝑨 simetris maka ruang baris 𝑨𝑨 ( Row 𝑨𝑨 ) sama dengan 𝐶𝐶𝐶𝐶𝐶𝐶 𝑨𝑨 . Dari definisi 2.5.12 tentang ruang baris dan Ruang null, diketahui bahwa 𝑅𝑅𝐶𝐶𝑅𝑅 ( 𝑨𝑨 ) sama dengan komplemen orthogonal dari ruang null matriks 𝑨𝑨 , dinotasikan dengan 𝑁𝑁𝑁𝑁𝐶𝐶𝐶𝐶 ( 𝑨𝑨 ) . Karena  ruang null tidak berpengaruh pada elemenasi operasi baris Gauss Jordan, maka didapatkan matriks 𝑬𝑬 yaitu bentuk eselon baris tereduksi dari matriks 𝑨𝑨 . Sehingga dapat disimpulkan bahwa 𝑁𝑁𝑁𝑁𝐶𝐶𝐶𝐶 ( 𝑨𝑨 ) = 𝑁𝑁𝑁𝑁𝐶𝐶𝐶𝐶 ( 𝑬𝑬 ) . Karena 𝑁𝑁𝑁𝑁𝐶𝐶𝐶𝐶 ( 𝑨𝑨 ) = 𝑁𝑁𝑁𝑁𝐶𝐶𝐶𝐶 ( 𝑬𝑬 )
maka 𝒃𝒃 dapat diselesaikan jika dan hanya jika 𝒃𝒃 termuat dalam komplemen orthogonal dari 𝑁𝑁𝑁𝑁𝐶𝐶𝐶𝐶 ( 𝐸𝐸 ) . Untuk menunjukkan bahwa 𝒃𝒃 termuat dalam komplemen orthogonal, maka harus dicari basis dari 𝑁𝑁𝑁𝑁𝐶𝐶𝐶𝐶 ( 𝑬𝑬 ) . matriks 𝑬𝑬 adalah sebuah sistem persamaan yang merupakan penyelesaian untuk variabel takbebas. Didapat persamaan
0 = 𝑒𝑒 1 + 𝑒𝑒 15 0 = 𝑒𝑒 2 + 𝑒𝑒 16
0 = 𝑒𝑒 3 + 𝑒𝑒 15 + 𝑒𝑒 16 ⋮
0 = 𝑒𝑒 14 + 𝑒𝑒 15 + 𝑒𝑒 16 Karena perhitungan dilakukan dalam modulo 2 maka didapat 𝑒𝑒 1 = 𝑒𝑒 15 𝑒𝑒 2 = 𝑒𝑒 16 𝑒𝑒 3 = 𝑒𝑒 15 + 𝑒𝑒 16 ⋮ = ⋮ 𝑒𝑒 14 = 𝑒𝑒 15 + 𝑒𝑒 16 𝑒𝑒 15 = 𝑒𝑒 15 𝑒𝑒 16 = 𝑒𝑒 16
Bentuk diatas dapat ditulis dalam bentuk basis sehingga didapat
⎣ ⎢ ⎢ ⎢ ⎢ ⎡ 𝑒𝑒 1 𝑒𝑒 2 𝑒𝑒 3 ⋮ 𝑒𝑒 14 𝑒𝑒 15 𝑒𝑒 16 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤ = 𝑒𝑒 15 ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ 1 0 1 ⋮ 0 1 0 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤ + 𝑒𝑒 16 ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ 0 1 1 ⋮ 1 0 1 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤
Dari persamaan diatas didapat bahwa basis dari 𝑁𝑁𝑁𝑁𝐶𝐶𝐶𝐶 ( E ) adalah 𝒏𝒏 𝟏𝟏 dan 𝒏𝒏 𝟐𝟐 . Untuk membuktikan bahwa kedua bentuk vektor  adalah basis orthogonal maka hasil kali titik kedua vektor adalah nol.
𝒏𝒏 𝟏𝟏 . 𝒏𝒏 𝟐𝟐 = ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ 1 0 1 ⋮ 0 1 0 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤ . ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ 0 1 1 ⋮ 1 0 1 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤ = (0 + 0 + 1 + ⋯ + 0) 𝑚𝑚𝐶𝐶𝑚𝑚 2  = 4 𝑚𝑚𝐶𝐶𝑚𝑚 2 = 0
Didapat 𝒏𝒏 𝟏𝟏 . 𝒏𝒏 𝟐𝟐 = 𝟎𝟎 , sehinggga terbukti bahwa 𝒏𝒏 𝟏𝟏 dan 𝒏𝒏 𝟐𝟐 adalah basis dari 𝑁𝑁𝑁𝑁𝐶𝐶𝐶𝐶 ( E ) dan terbukti bahwa 𝒃𝒃 konsisten jika dan hanya jika orthogonal dengan vektor 𝒏𝒏 𝟏𝟏 dan 𝒏𝒏 𝟐𝟐 . ∎ Teorema 4.2.2 Jika konfigurasi 𝑏𝑏�⃗ dapat diselesaikan maka ada empat strategi untuk mencari solusi optimal permainan yaitu
𝑥𝑥⃗ = 𝑅𝑅𝑏𝑏�⃗
𝑥𝑥⃗ = 𝑅𝑅𝑏𝑏�⃗ + 𝑛𝑛 1 𝑥𝑥⃗ = 𝑅𝑅𝑏𝑏�⃗ + 𝑛𝑛 1 + 𝑛𝑛 2 𝑥𝑥⃗ = 𝑅𝑅𝑏𝑏�⃗ + 𝑛𝑛 2 𝑅𝑅 adalah hasil dari matriks elementer yang didapat dari eselon baris tereduksi, 𝑅𝑅𝐴𝐴 = 𝐸𝐸 .
Bukti:
Matriks 𝑬𝑬 memiliki dua variabel bebas yaitu 𝑥𝑥 15 dan 𝑥𝑥 16 maka ada 4 kemungkinan yang mungkin terjadi, yaitu
𝑥𝑥 15 = 0 dan 𝑥𝑥 16 = 0 𝑥𝑥 15 = 1 dan 𝑥𝑥 16 = 0 𝑥𝑥 15 = 0 dan 𝑥𝑥 16 = 1 𝑥𝑥 15 = 1 dan 𝑥𝑥 16 = 1 pertama, pilih 𝑥𝑥 15 = 0 dan 𝑥𝑥 16 = 0 . Maka  didapat bahwa 𝐸𝐸𝑥𝑥⃗ = 𝑥𝑥⃗ , persamaan ini di subtitusikan ke 𝑅𝑅𝐴𝐴 = 𝐸𝐸 dan 𝐴𝐴𝑥𝑥⃗ = 𝑏𝑏�⃗ maka didapat 𝑥𝑥⃗ = 𝐸𝐸𝑥𝑥⃗ = 𝑅𝑅𝐴𝐴𝑥𝑥⃗ = 𝑅𝑅𝑏𝑏�⃗
Pilih 𝑥𝑥 15 = 1 dan 𝑥𝑥 16 = 0 , Maka didapat 𝑥𝑥⃗ = 𝐸𝐸 ( 𝑥𝑥⃗ + 𝑛𝑛�⃗ 1 ) , persamaan ini disubtitusikan ke 𝑅𝑅𝐴𝐴 = 𝐸𝐸 dan 𝐴𝐴𝑥𝑥⃗ = 𝑏𝑏�⃗ maka didapat 𝑥𝑥⃗ = 𝐸𝐸 ( 𝑥𝑥⃗ + 𝑛𝑛�⃗ 1 ) = 𝐸𝐸𝑥𝑥⃗ + 𝐸𝐸𝑛𝑛�⃗ 1 = 𝑅𝑅𝐴𝐴𝑥𝑥⃗ + 𝐸𝐸𝑛𝑛�⃗ 1 = 𝑅𝑅𝑏𝑏�⃗ + 𝑛𝑛�⃗ 1 Pilih 𝑥𝑥 15 = 0 dan 𝑥𝑥 16 = 1 , maka didapat 𝑥𝑥⃗ = 𝐸𝐸 ( 𝑥𝑥⃗ + 𝑛𝑛�⃗ 1 ) , persamaan ini disubtitusikan ke 𝑅𝑅𝐴𝐴 = 𝐸𝐸 dan 𝐴𝐴𝑥𝑥⃗ = 𝑏𝑏�⃗ maka didapat. 𝑥𝑥⃗ = 𝐸𝐸 ( 𝑥𝑥⃗ + 𝑛𝑛�⃗ 2 ) = 𝐸𝐸𝑥𝑥⃗ + 𝐸𝐸𝑛𝑛�⃗ 2 = 𝑅𝑅𝐴𝐴𝑥𝑥⃗ + 𝐸𝐸𝑛𝑛�⃗ 2 = 𝑅𝑅𝑏𝑏�⃗ + 𝑛𝑛�⃗ 2 Pilih 𝑥𝑥 15 = 1 dan 𝑥𝑥 16 = 1 , maka didapat 𝑥𝑥⃗ = 𝐸𝐸 ( 𝑥𝑥⃗ + 𝑛𝑛�⃗ 1 + 𝑛𝑛�⃗ 2 ) , persamaan ini disubtitusikan ke 𝑅𝑅𝐴𝐴 = 𝐸𝐸 dan 𝐴𝐴𝑥𝑥⃗ = 𝑏𝑏�⃗ maka didapat 𝑥𝑥⃗ = 𝐸𝐸 ( 𝑥𝑥⃗ + 𝑛𝑛�⃗ 1 + 𝑛𝑛�⃗ 2 ) = 𝐸𝐸𝑥𝑥⃗ + 𝐸𝐸𝑛𝑛�⃗ 1 + 𝐸𝐸𝑛𝑛�⃗ 2 = 𝑅𝑅𝐴𝐴𝑥𝑥⃗ + 𝐸𝐸𝑛𝑛�⃗ 1 + 𝐸𝐸𝑛𝑛�⃗ 2 = 𝑅𝑅𝑏𝑏�⃗ + 𝑛𝑛�⃗ 1 + 𝑛𝑛�⃗ 2 ∎
Jadi untuk permainanan light out 4x4 memiliki 4 solusi yaitu
𝑥𝑥⃗ = 𝑅𝑅𝑏𝑏�⃗ 𝑥𝑥⃗ = 𝑅𝑅𝑏𝑏�⃗ + 𝑛𝑛 1 𝑥𝑥⃗ = 𝑅𝑅𝑏𝑏�⃗ + 𝑛𝑛 2 𝑥𝑥⃗ = 𝑅𝑅𝑏𝑏�⃗ + 𝑛𝑛 1 + 𝑛𝑛 2
Untuk  matriks 5x5 dengan eliminasi Gauss jordhan didapat matriks G dengan rank 24 dan memiliki satu variabel bebas yaitu 𝑥𝑥 25 .  Sistem persamaan 𝑨𝑨𝑨𝑨 = 𝒃𝒃 memiliki solusi jika dan hanya jika 𝒃𝒃 orthogonal dengan dua vektor 𝒏𝒏 𝟏𝟏 ,  dimana 𝒏𝒏 𝟏𝟏 adalah elemen pada kolom ke-25 (ruang null), dimana diambil 𝑥𝑥 25 = 1
𝒏𝒏 𝟏𝟏 = (1,0,1,0,1,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,1,0,1,0,1)
Jika konfigurasi b �⃗ dapat diselesaikan maka ada dua strategi untuk mencari solusi optimal permainan yaitu
𝑥𝑥⃗ = 𝑅𝑅𝑏𝑏�⃗ 𝑥𝑥⃗ = 𝑅𝑅𝑏𝑏�⃗ + 𝑛𝑛 1 R adalah hasil dari matriks elementer yang didapat dari eselon baris tereduksi, 𝑅𝑅𝐴𝐴 = 𝐸𝐸 . Bukti: Matriks 𝑬𝑬 memiliki satu variabel bebas yaitu 𝑥𝑥 25 maka ada 2 kemungkinan yang mungkin terjadi, yaitu
𝑥𝑥 25 = 0 atau 𝑥𝑥 25 = 1 pertama, pilih 𝑥𝑥 25 = 0 . Maka  didapat bahwa 𝐸𝐸𝑥𝑥⃗ = 𝑥𝑥⃗ , persamaan ini di subtitusikan ke 𝑅𝑅𝐴𝐴 = 𝐸𝐸 dan 𝐴𝐴𝑥𝑥⃗ = 𝑏𝑏�⃗ maka didapat 𝑥𝑥⃗ = 𝐸𝐸𝑥𝑥⃗ = 𝑅𝑅𝐴𝐴𝑥𝑥⃗ = 𝑅𝑅𝑏𝑏�⃗ 𝑥𝑥 25 = 1 , maka didapat 𝑥𝑥⃗ = 𝐸𝐸 ( 𝑥𝑥⃗ + 𝑛𝑛�⃗ 1 ) , persamaan ini disubtitusikan ke 𝑅𝑅𝐴𝐴 = 𝐸𝐸 dan 𝐴𝐴𝑥𝑥⃗ = 𝑏𝑏�⃗ maka didapat.
𝑥𝑥⃗ = 𝐸𝐸 ( 𝑥𝑥⃗ + 𝑛𝑛�⃗ 1 ) = 𝐸𝐸𝑥𝑥⃗ + 𝐸𝐸𝑛𝑛�⃗ 1 = 𝑅𝑅𝐴𝐴𝑥𝑥⃗ + 𝐸𝐸𝑛𝑛�⃗ 1 = 𝑅𝑅𝑏𝑏�⃗ + 𝑛𝑛�⃗ 1 ∎
Sehingga untuk light out ukuran sedangkan untuk 5 × 5 jika memiliki dua  solusi, yaitu 𝑨𝑨��⃗ = 𝑹𝑹𝒃𝒃 , 𝑨𝑨��⃗ = 𝑹𝑹𝒃𝒃��⃗ + 𝒏𝒏 𝟏𝟏

## 5. KESIMPULAN
1. Permainan light out yang berukuran 3 × 3 memiliki solusi untuk setiap 𝒃𝒃 (kondisi awal permainan), misalkan 𝑏𝑏 = (1 0 1 1 0 1 1 0 1) 𝑇𝑇 maka solusinya 𝑨𝑨 = ( 𝟎𝟎 , 𝟎𝟎 , 𝟎𝟎 , 𝟏𝟏 , 𝟎𝟎 , 𝟏𝟏 , 𝟎𝟎 , 𝟎𝟎 , 𝟎𝟎 ) 𝑻𝑻 sedangkan untuk ukuran 4 × 4 memiliki solusi jika 𝒃𝒃 ortogonal dengan 𝒏𝒏 1 dan 𝒏𝒏 𝟐𝟐 , misalkan 𝒃𝒃 = (1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 ) 𝑇𝑇 maka permainan memiliki solusi dan solusinya 𝑨𝑨 = (1 0 0 1 0 1 1 0 1 0 0 1 0 0 0 0) 𝑇𝑇 dan untuk 5 × 5 memiliki solusi jika 𝒃𝒃 ortogonal dengan 𝒏𝒏 𝟏𝟏 , misalkan 𝒃𝒃 = (1 1 0 1 1 1 1 0 1 1 0 0 0 0 0 1 1 0 1 1 1 1 0 1 1)
𝑇𝑇 maka permainan memiliki solusi dan solusinya 𝑨𝑨 = (0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 0) 𝑇𝑇 .
2. Permainan light out yang berukuran 3 × 3 memiliki solusi yang tunggal yaitu 𝑨𝑨 = 𝑨𝑨 −𝟏𝟏 𝒃𝒃 sedangkan permainan light out yang berukuran 4 × 4 jika memiliki solusi,  solusinya  yaitu 𝑨𝑨��⃗ = 𝑹𝑹𝒃𝒃 , 𝑨𝑨��⃗ = 𝑹𝑹𝒃𝒃��⃗ + 𝒏𝒏 𝟏𝟏 , 𝑨𝑨��⃗ = 𝑹𝑹𝒃𝒃��⃗ + 𝒏𝒏 𝟐𝟐 , 𝑨𝑨 ���⃗ = 𝑹𝑹𝒃𝒃��⃗ + 𝒏𝒏 𝟏𝟏 + 𝒏𝒏 𝟐𝟐
misalkan  dan permainan memiliki solusi  sedangkan untuk 5 × 5 jika memiliki solusi, solusinya ada dua yaitu 𝑨𝑨��⃗ = 𝑹𝑹𝒃𝒃 , 𝑨𝑨��⃗ = 𝑹𝑹𝒃𝒃��⃗ + 𝒏𝒏 𝟏𝟏 dan  solusi optimalnya adalah yang memiliki penekanan tombol paling sedikit.

## DAFTAR PUSTAKA
[1]Anderson, Marlow.1998. Turning Light Out with Algebra .Vol.71, No.74 pp. 300- 303 Mathematical Assosiation Of America.
[2]Delin, Tan. Linear  algebra analyzing on light out game. Journal of science & Mathematics Education Vol. 9 No.1.
[3]Howard, Anton. 2000. Dasar-  Dasar Aljabar Linier.Edisi 7 jilid 1 . Interaksara:Batam
[4]Madsen, Matthew A. 2010. Light out Solutions Using Linear Algebra . Disajikan Mei 2010, hal 36-40.http://ripon.edu/macs/summation.
[5]Mulholland, Jamie. 2016. Permutation Puzzle A mathematical perspective . Departement Of mathematics Simon fraser University.