כיבוי אורות (או: תורת הגרפים והאלגברה הלינארית מחסלות עוד משחק תמים)

“כיבוי אורות”, או Lights Out הוא משחק תמים שהולך כך: נתון לוח משבצות של \( 5\times5 \), כך שכל משבצת יכולה להיות מוארת או כבויה; נניח מכאן ואילך עד לסוף הפוסט (כמעט) שבתחילת המשחק כל המשבצות כבויות. כל לחיצה על משבצת משנה את מצב המשבצת ומצב כל השכנות שלה: משבצת שהייתה כבויה נדלקת, ומשבצת שהייתה דלוקה כבה. המטרה: להגיע למצב שבו כל הנורות דולקות.

אוהו, אומרים ותיקי הבלוג. עוד משחק בלתי פתיר ועוד אינוריאנטים מעיקים. ובכן, לא הפעם. המשחק פתיר, ולא סתם - אני רוצה להראות שבעצם כל המשחקים מסוגו פתירים. אציג שתי הוכחות - האחת קומבינטורית באופיה, והשניה (של נגה אלון) מבוססת על אלגברה לינארית.

האופן הטבעי להכליל את הבעיה הוא לדבר על גרף (אניח שהקוראים מכירים את המושג הזה). המשבצות הן צמתים, וקשת בין שני צמתים מייצגת משבצות שכנות. בצורה הזו אפשר לייצג לוח \( n\times n \) ריבועי כלשהו; וגם לוחות מלבניים; ועם משושים או משולשים; או תלת ממדיים, או כל דבר בעצם. אני לא אניח שום דבר על הגרף שאני תוקף.

הדבר הראשון שצריך לשים לב אליו הוא שאמנם טבעי לחשוב על המשחק בגישה “סדרתית” (“קודם אלחץ כאן ואז אלחץ שם”) אבל זה מיותר לגמרי. אין שום חשיבות לסדר שבו לוחצים על משבצות, וגם אין שום צורך ללחוץ על משבצת יותר מפעם אחת (לחיצה כפולה פשוט מנטרלת את האפקט של הלחיצה הראשונה; אם לחצנו פעמיים, גם אם חלף פרק זמן גדול בין הלחיצות ועשינו דברים אחרים בלוח, זה שקול לחלוטין לכך שמעולם לא היינו לוחצים וחסל). כלומר, הדרך ה”נכונה” לנצח במשחק היא פשוט ללחוץ בו זמנית על קבוצה מסויימת של צמתים, וזהו. פורמלית, אם \( V \) היא קבוצת צמתי הגרף, אנו מחפשים תת-קבוצה \( S\subseteq V \) כך שלכל צומת \( v\notin S \) יש מספר אי זוגי של שכנים מתוך \( S \), ואילו לכל צומת \( v\in S \) יש מספר זוגי של שכנים מתוך \( S \) (זוגי, כי אנחנו נלחץ גם על \( v \) עצמו, ואנחנו רוצים שכל הלחיצות שלנו על השכנים של \( v \) יבטלו אלו את אלו בכל מה שנוגע ל-\( v \)).

כאן אני שולף מהשרוול שפן בדמות טענה לא טריוויאלית לגמרי בתורת הגרפים - לכל גרף אפשר לפרק את קבוצת הצמתים שלו לשתי קבוצות זרות \( V_{1},V_{2} \) כך שבתת-הגרפים המושרים על \( V_{1},V_{2} \) כל הצמתים הם מדרגה זוגית. תכף אוכיח את הטענה הזו אבל בואו נבין איך נעזרים בה כדי להראות שקיימת בגרף קבוצה \( S \) כמו שאנחנו רוצים. הרעיון הוא לבצע בניית עזר - לקחת את הגרף של המשחק, ולהוסיף צומת חדשה \( u \) שמחוברת לכל צומת בגרף שדרגתו זוגית. כעת אפשר לחלק את הגרף לשתי קבוצות \( V_{1},V_{2} \) כאמור לעיל. בואו נניח ש-\( u\in V_{2} \), בלי הגבלת הכלליות; אז נגדיר \( S=V_{1} \).

כעת, מה הולך כאן? מצד אחד, הדרגה של כל צומת בתת-הגרף שמושרה על \( S \) היא זוגית, מה שאומר בדיוק שלכל \( v\in S \) יש מספר זוגי של שכנים ב-\( S \); מצד שני, אם \( v\notin S \) והוא מחובר ל-\( u \), זה אומר שהוא מחובר למספר זוגי של צמתים שאינם ב-\( S \) כולל הצומת החדש \( u \). זה שאומר ש-\( v \) מחובר למספר אי זוגי של צמתים שאינם ב-\( S \) ואינם \( u \). כעת מגיע טיעון המחץ: את \( u \) חיברנו רק לצמתים שהיו מדרגה זוגית מלכתחילה, ולכן אם \( v \) מחובר למספר אי זוגי של צמתים שאינם מ-\( S \) ודרגתו לפני הוספת \( u \) לגרף הייתה זוגית, הוא חייב להיות מחובר למספר אי זוגי של צמתים מ-\( S \). אם לעומת זאת \( v \) לא מחובר ל-\( u \) זה אומר שדרגתו בגרף המקורי הייתה אי זוגית, וכעת הוא מחובר למספר זוגי של צמתים שאינם ב-\( S \) ולכן גם כאן הוא חייב להיות מחובר למספר אי זוגי של צמתים מ-\( S \). סוף המשחק.

טוב ויפה, אבל איך מוצאים פירוק ל-\( V_{1},V_{2} \) שכזה? אם בגרף שלנו כל הצמתים מדרגה זוגית אז \( V_{1}=V,V_{2}=\emptyset \) הוא פירוק טריוויאלי שכזה (ועל הדרך יש בגרף מעגל אוילרי) אבל אפשר לצפות שבאופן כללי יהיה בגרף איזה צומת \( v \) שהוא מדרגה לא זוגית. אם כן, הופס! נוציא את \( v \) מהגרף.

למרבה הצער, זה לא מספיק. נצטרך לעשות התחכמות נוספת שחשיבותה תתברר בקרוב. בואו נסמן ב-\( S \) את קבוצת השכנים של \( v \) בגרף; לכל זוג צמתים \( x,y\in S \), אם יש קשת בין \( x,y \) נוריד אותה מהגרף, ואם אין קשת - נוסיף אותה לגרף.

אם כן, על ידי הוצאת \( v \) קיבלנו גרף קטן יותר (עם פחות צמתים) ולכן אפשר לשלוף מהכיס את קסם ההוכחה באינדוקציה ולטעון שבגרף הקטן יותר יש חלוקה לשתי קבוצות \( W_{1},W_{2} \) כך שדרגת כל צומת בתת-הגרף שמושרה על ידי כל אחת מהקבוצות היא זוגית. מה שנרצה לעשות הוא להחזיר את \( v \) לאחת מהקבוצות הללו, אבל לאיזו מהן? מכיוון ש-\( S \) אי-זוגית, בהכרח \( S\cap W_{1} \) אי זוגית או \( S\cap W_{2} \) אי זוגית (אחרת היה אפשר לכתוב מספר אי זוגי כסכום שני מספרים זוגיים). בואו נניח ש-\( S\cap W_{1} \) זוגית - אני טוען שלהוסיף את \( v \) לקבוצה הזו יסיים את העסק. כלומר, נגדיר \( V_{1}=W_{1}\cup\left\{ v\right\} \) ו-\( V_{2}=W_{2} \). נותר רק להבין למה זה עובד.

ברור כי כל צמתי \( V \) שלא היו שייכים ל-\( S \) ואינם \( v \) עדיין מקיימים את תכונת הזוגיות הנדרשת - מבחינתם לא שיניתי כלום. לעומת זאת, צמתי \( S\cap W_{1} \) חוו טראומה כפולה - גם חיברו להם את \( v \) (ובכך שינו להם את הזוגיות) וגם הפכו את הקשתות בינם לבין עצמם. כל איבר של \( S \) היה מחובר למספר אי זוגי של שכנים מתוך \( S \) ב-\( W_{1} \), מה שאומר שמספר השכנים מתוך \( S \) ב-\( W_{1} \) שהוא לא היה מחובר אליהם היה בעל סימן הפוך, ולכן אחרי היפוך הקשתות הזוגיות משתנה ומבטלת את שינוי הזוגיות ש-\( v \) גרם לו.

מבלבל? בהחלט. בואו נראה דוגמת צעצוע. נניח ש-\( S\cap W_{1} \) הייתה מגודל 6. נסתכל על צומת \( x\in S\cap W_{1} \) כלשהו. יש לו בדיוק 5 שכנים פוטנציאליים שגם הם ב-\( S\cap W_{1} \). נניח שכרגע יש לו קשת ל-2 מהם, זה אומר שאין קשת ל-3, ואחרי שנהפוך את זה (נמחק את הקשתות הקיימות וניצור את כל הקשתות שלא היו קודם) הזוגיות של הדרגה של \( x \) תשתנה בשל כך (קודם היא הייתה זוגית, עכשיו היא כבר לא). אם לעומת זאת הייתה קשת מ-\( x \) רק לצומת אחד אחר ב-\( S\cap W_{1} \) אחרי השינוי תהיה קשת ל-4: שוב שינוי בזוגיות. תוסיפו לכך את השינוי בזוגיות ש-\( v \) גורם לו, וקיבלנו שגם ב-\( V_{1} \) האיבר \( x \) מחובר רק למספר זוגי של צמתים.

עכשיו כבר די ברור מה קורה ב-\( S\cap W_{2} \), אני מקווה. אנחנו לא מוסיפים את \( v \) לשם כך שהוא לא גורם לשום שינוי. מצד שני, גם היפוך הקשתות לא יגרום לשום שינוי, כי לכל צומת \( x\in S\cap W_{2} \) יש מספר שכנים פוטנציאלי זוגי מתוך \( S\cap W_{2} \). לכן: או שקודם \( x \) היה מחובר למספר זוגי, ואחרי השינוי הוא עדיין יהיה מחובר למספר זוגי, או שקודם הוא היה מחובר למספר אי זוגי, ואחרי השינוי הוא עדיין יהיה מחובר למספר אי זוגי. סיימנו.

ההוכחה הזו עלולה להיראות מסורבלת ממבט ראשון אבל אני חושב שהיא אלגנטית למדי. יתרון חשוב שלה היא שזו הוכחה קונסטרוקטיבית - אפשר לחלץ ממנה אלגוריתם רקורסיבי שממש מוצא את הפתרון ורץ בזמן סביר. די בכך כדי לסגור את סיפור המשחק הזה, אבל אני רוצה להציג את נקודת המבט של האלגברה הלינארית על העניין - כפי שנראה, במובנים מסויימים היא חזקה וכללית יותר.

כבר הזכרתי בפוסט על כפל מטריצות את הרעיון לפיו אפשר לייצג גרף באמצעות מטריצה, ובכך להכניס את האלגברה הלינארית לתורת הגרפים בדלת הקדמית. אם הגרף מכיל את הצמתים \( \left\{ v_{1},\dots,v_{n}\right\} \) אז המטריצה, שאסמן \( A \), תהיה מסדר \( n\times n \), כך שהכניסה \( A_{ij} \) שווה 1 אם יש קשת בין \( v_{i} \) ו-\( v_{j} \) ו-0 אחרת. במקרה שלנו הגרף איננו מכוון כך ש-\( A_{ij}=A_{ji} \) - המטריצה סימטרית. מכיוון שהמטריצה מכילה רק 0 ו-1 ואין משמעות לערכים אחרים, הגיוני לחשוב עליה בתור מטריצה מעל השדה הפצפון \( \mathbb{F}_{2}=\left\{ 0,1\right\} \) (אלגברה לינארית תמיד עושים מעל שדה, אחרת תוצאות בסיסיות - כמו זה שאפשר לדרג כל מטריצה - פשוט לא עובדות יותר).

כעת, מה המשמעות של כפל המטריצה \( A \) בוקטור \( x \) כלשהו מעל \( \mathbb{F}_{2} \)? התוצאה תהיה וקטור \( u \) כך ש-\( y_{i}=\sum_{j=1}^{n}A_{ij}x_{j} \), כלומר \( y_{i} \) הוא מספר האינדקסים \( j\in\left\{ 1,\dots,n\right\} \) כך שבו זמנית \( A_{ij}=1 \) וגם \( x_{j}=1 \). חשבו על \( x_{j}=1 \) כאומר “בחרנו ללחוץ על \( x_{j} \) בפתרון שלנו”, ואז \( y_{i} \) מתאר בדיוק מה יהיה המצב של הצומת \( v_{i} \) אחרי הלחיצות - אנחנו עוברים על כל צומת שמחובר ל-\( v_{i} \) בקשת ואם רואים שבחרנו ללחוץ עליו, אנחנו מוסיפים 1 ל-\( y_{i} \) ובסופו של דבר (בגלל שאנחנו מעל \( \mathbb{Z}_{2} \)) נקבל ש-\( y_{i} \) מכיל את זוגיות מספר הלחיצות. שימו לב שבשביל שזה יעבוד אנחנו חייבים לקבוע ש-\( A_{ii}=1 \) לכל \( i \), כי הרי לחיצה על צומת משנה גם את מצבו שלו (אפשר - וכדאי - לחשוב על כך כאילו יש קשת מהצומת לעצמו וחסל).

אם לסכם, מה שאנחנו רוצים לעשות הוא פשוט לפתור את המשוואה \( Ax=\overline{1} \), כאשר \( \overline{1} \) הוא הוקטור שכולו אחדות (ואם הלוח התחיל ממצב אחר שבו לא כל המשבצות כבויות, פשוט יש משוואה שונה שאפשר לנסות לפתור - אבל במקרה הזה לא מובטח שהיא תהיה פתירה בהכרח; נסו למצוא לוח לא פתיר!). הנה הצלחנו לתרגם עוד בעיה קומבינטורית לגמרי לבעיה בסיסית של אלגברה לינארית. האופן שבו פותרים את הבעיה ידוע - דירוג מטריצות, שניתן לביצוע באופן כללי ביעילות סבירה - ועיקר העניין כרגע הוא בהוכחה שתמיד קיים פתרון. ההוכחה עצמה היא עניין של שורה או שתיים שמבוססות על תוצאות סטנדרטיות באלגברה לינארית - אבל תוצאות שטרם הראיתי, וזו הזדמנות טובה לראות להן דוגמה קונקרטית לפני שמציגים את התורה הכללית.

בתור התחלה, שימו לב ש-\( Ax \) הוא בעצם צירוף לינארי של עמודות \( A \) שמקדמיו נקבעים לפי הכניסות של \( x \). באופן דומה, \( xA \) הוא צירוף לינארי של שורות \( A \) (כרגיל, אני ממשיך במנהג הנלוז שלי לכתוב \( x \) גם לוקטור שורה וגם לוקטור עמודה מתוך הנחה שתבינו מההקשר: \( Ax \) הוא מכפלה של \( A \) בוקטור עמודה, ואילו \( xA \) הוא מכפלה של \( A \) בוקטור שורה). במקרה שלנו \( A \) סימטרית, ולכן אם משהו נמצא בתמונה של \( A \) (כלומר, מתקבל על ידי כפל \( Ax \)) הוא נמצא במרחב שנפרש על ידי שורות \( A \) ולהיפך. נשארנו עם להוכיח ש-\( \overline{1} \) נמצא במרחב שנפרש על ידי שורות \( A \). את המרחב הזה קל במיוחד להבין על ידי התבוננות בגרעין של \( A \), \( \ker A \) - כל הוקטורים \( c \) שמקיימים \( Ac=\overline{0} \).

שימו לב לכך שאם יש לנו \( c\in\ker A \) אז מתקיים \( \left(xA\right)c=x\left(Ac\right)=x\overline{0}=0 \). במילים: אם ניקח וקטור כלשהו שנפרש על ידי שורות \( A \) ונכפול אותו עם איבר של \( \ker A \), נקבל 0. אם הרעיון של כפל שני וקטורים מבלבל אתכם, זכרו שהאחד הוא וקטור שורה והשני וקטור עמודה ואפשר לחשוב על הכפל כמכפלה של מטריצה \( 1\times n \) במטריצה \( n\times1 \). אפשר גם לחשוב על זה כך: אם \( x=\left(x_{1},\dots,x_{n}\right) \) ו-\( y=\left(y_{1},\dots,y_{n}\right) \), אפשר להגדיר מכפלה שלהם על ידי \( x\cdot y=\sum_{i=1}^{n}x_{i}y_{i} \). זה זהה לחלוטין למה שמתקבל מכפל המטריצות, אבל אנחנו כבר לא צריכים להטריד את עצמנו בעניינים כמו מי וקטור שורה ומי וקטור עמודה. המכפלה שהגדרתי כרגע נקראת מכפלה סקלרית של וקטורים, ועוד נפגוש בה בהמשך הפוסטים על אלגברה לינארית.

אם \( x\cdot y=0 \) אומרים ש-\( x,y \) אורתוגונליים (מאונכים), מסיבות גאומטריות שיובהרו בפעם אחרת. לעת עתה, מה שראינו הוא שכל איבר במרחב השורות של \( A \) אורתוגונלי לכל איבר בגרעין של \( A \). אני רוצה לטעון שגם ההפך הוא נכון - אם \( x \) אורתוגונלי לכל איבר בגרעין של \( A \), אז \( x \) נמצא במרחב השורות של \( A \).

לב הענין הוא בטענה הבאה: אם \( V \) הוא מרחב וקטורי כלשהו, ואם \( W \) הוא תת מרחב כלשהו, ואם \( W^{\perp}=\left\{ x|\forall y\in W:xy=0\right\} \) הוא אוסף כל האיברים ב-\( V \) שאורתוגונליים לכל איברי \( W \), אז \( \dim V=\dim W+\dim W^{\perp} \). לא אוכיח כרגע את התכונה הזו אבל אני מקווה שאסגור את החשבון באחד מהפוסטים העתידיים. כדי להבין איך הטענה הזו עוזרת לנו, זכרו שמתקיים \( \dim V=\dim\ker A+\dim\mbox{Im}A \) - זו תכונה חשובה של טרנספורמציות לינאריות שכבר הוכחתי בעבר. אם \( W=\ker A \) אז חיבור שני השוויונות מראה לנו שמימד מרחב השורות של \( A \) הוא כמימד \( W^{\perp} \) ומכיוון שידוע לנו שמרחב השורות מוכל ב-\( W^{\perp} \) עולה שהם שווים, מה שמסיים את הוכחת הטענה שאם וקטור אורתוגנלי לכל הגרעין אז הוא במרחב השורות.

כל שנותר לעשות הוא להוכיח שהוקטור \( \overline{1} \) אורתוגונלי לכל איבר בגרעין של \( A \). לצורך כך אנחנו שולפים מהשרוול את התעלול האחרון שלנו, שעובד רק מעל \( \mathbb{F}_{2} \). ניקח וקטור כלשהו \( v \). מהו \( vAv \)? אם נחשב לפי ההגדרה הישירה, נקבל ש-

\( vAv=v\cdot\left(\sum_{i=1}^{n}A_{1i}v_{i},\dots,\sum_{i=1}^{n}A_{ni}v_{i}\right)=\sum_{j=1}^{n}v_{j}\left(\sum_{i=1}^{n}A_{ji}v_{i}\right)=\sum_{i,j=1}^{n}A_{ji}v_{i}v_{j} \)

בהערת אגב אציין שהרעיון הזה, של לכפול מטריצה מימין ומשמאל בוקטור כדי לקבל סקלר, הוא מה שעומד בלב המושג של תבניות בילינאריות שאני מקווה להגיע אליהן בהמשך. מה שקורה כרגע הוא מקרה פרטי שבו העסק פשוט הרבה יותר בגלל שאנחנו מעל \( \mathbb{F}_{2} \) ובגלל ש-\( A \) סימטרית. שימו לב שבגלל הסימטריה הזו, \( A_{ji}=A_{ij} \) ואם \( i\ne j \) אז בסכום מופיעים גם \( A_{ji}v_{j}v_{i} \) וגם \( A_{ij}v_{i}v_{j} \) והסכום של שניהם הוא פשוט \( 2A_{ij}v_{j}v_{i}=0 \) - אפס, כי אנחנו ב-\( \mathbb{F}_{2} \). לכן מכל הסכום נותר לנו רק \( \sum_{i=1}^{n}A_{ii}v_{i}^{2} \). בגלל שאנחנו מעל \( \mathbb{F}_{2} \), אז \( v_{i}^{2}=v_{i} \) (כי \( v_{i}\in\left\{ 0,1\right\} \)), ולכן קיבלנו שנותר לנו רק \( \sum_{i=1}^{n}A_{ii}v_{i} \) - וזו, במילים אחרות, המכפלה הסקלרית של האלכסון של \( A \) עם הוקטור \( v \).

כעת, אם \( v \) בגרעין של \( A \), אז \( Av=0 \) ולכן בוודאי \( vAv=0 \), ולכן האלכסון של \( A \) אכן אורתוגונלי לגרעין של \( A \) וההוכחה נסתיימה. אולי היא נראית קצת מסורבלת ומוזרה כעת, אבל למי שבקיא במושגים היא לא דורשת יותר משורה-שתיים.

אם כן, איזו הוכחה מבין השתיים שהצגתי עדיפה? התשובה פשוטה - אף אחת מהן. ריבוי הוכחות עם אופי שונה הוא דבר נפלא במתמטיקה, וממש לא צריך להשוות.