משפט המטריצה-עץ של קירכהוף

אני רוצה לדבר הפעם על מה שלטעמי הוא משפט יפהפה ביותר, גם בשל מה שהוא אומר וגם בשל ההוכחה שלו, שלטעמי מייצגת את כל מה שטוב במתמטיקה - גם דורשת הבנה טכנית לא טריוויאלית, וגם מכילה תובנה עמוקה שמאפשרת לראות מדוע המשפט נכון. העולם מסכים איתי, וההוכחה הזו מככבת בספר “Proofs from THE BOOK”; אני מקווה שכל מי שיתאמץ יצליח להבין אותה וליהנות כמוני ממנה.

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

ראשית אציג גרסה של המשפט שעוסקת בגרפים לא מכוונים כי ההוכחה שלו פשוטה מעט יותר; לאחר מכן אסביר כיצד ניתן להוכיח את המשפט גם לגרפים מכוונים (באותה הצורה אבל עם תיקונים קלים). המשפט בא לענות על השאלה הקומבינטורית הבאה: בהינתן גרף סופי \( G=\left(V,E\right) \), כמה עצים פורשים יש לו? כזכור, עץ פורש של \( G \) הוא תת-קבוצה של הקשתות שמהווה עץ (כלומר, כשמורידים מ-\( G \) את כל הקשתות שאינן בתת-הקבוצה נשארים עם גרף קשיר וחסר מעגלים). עובדה אחת שאתם אולי לא זוכרים והיא רלוונטית כאן היא שבגרף עם \( n=\left|V\right| \) צמתים, כל עץ הוא בעל בדיוק \( n-1 \) קשתות (נסו להוכיח זאת לעצמכם!)

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

בואו נכניס מטריצות לתמונה. יש כמה וכמה מטריצות שאפשר להתאים לכל גרף \( G \), ואחת מהן היא מטריצת הלפלסיאן \( L_{G} \) (ובקיצור אכתוב סתם \( L \)). ההגדרה של \( L \) אולי תיראה קצת מוזרה במבט ראשון אבל היא שימושית; למשל, עבור משפט קירכהוף.

ראשית, מכיוון שמטריצות מאונדקסות בדרך כלל עם מספרים טבעיים, הבה ונאנדקס גם את הגרף עם מספרים כאלו: \( V=\left\{ v_{1},\dots,v_{n}\right\} \) ו-\( E=\left\{ e_{1},\dots,e_{m}\right\} \). בדרך כלל כשאתייחס לצומת זה יהיה עם אינדקס \( i \) או \( j \), ולקשת עם אינדקס \( k \).

כעת אנו מוכנים להגדיר את \( L \): ראשית, \( L_{ii}=d\left(v_{i}\right) \), כלומר הכניסה ה-\( i \) על האלכסון של \( L \) היא פשוט הדרגה של \( v_{i} \) - מספר הקשתות שמחוברות ל-\( v_{i} \). כעת, לכל \( i\ne j \) נגדיר את \( L_{ij} \) להיות מינוס מספר הקשתות בין \( v_{i} \)ל-\( v_{j} \) (בדרך כלל יש רק קשת אחת בין כל שני צמתים בגרף, אבל כאן אנחנו מרשים יותר; כמובן שככל שיש יותר קשתות יהיו יותר עצים פורשים). אם נסמן את המספר הזה בסימון שהמצאתי כרגע, \( d\left(v_{i},v_{j}\right) \) ונסכים ש-\( d\left(v_{i},v_{i}\right) \) הוא פשוט דרגת \( v_{i} \) (במקום מספר הקשתות מ-\( v_{i} \) לעצמו), הרי שאפשר לכתוב את הלפלסיאן כך: \( L_{ij}=d\left(v_{i},v_{j}\right) \).

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

הגדרת הלפלסיאן עבור גרפים מכוונים כמעט זהה, בשני שינויים קלים: ראשית, \( L_{ii} \) הוא דרגת הכניסה של \( v_{i} \) - מספר הקשתות שנכנסות אליו - ולא הדרגה הכוללת; שנית, \( L_{ij} \) הוא מינוס מספר הקשתות מ-\( v_{i} \) אל \( v_{j} \) (כלומר, קשתות מ-\( v_{j} \) אל \( v_{i} \) לא נספרות ב-\( L_{ij} \), אם כי הן כן ייספרו ב-\( L_{ji} \)). לא קשה לראות שההגדרה הזו מכלילה את ההגדרה לגרפים לא מכוונים אם נוקטים בתעלול הרגיל של לייצג גרף לא מכוון על ידי גרף מכוון שבו לכל זוג צמתים שיש ביניהם קשת בגרף הלא מכוון, היא מוחלפת בקשת לכל אחד משני הכיוונים בגרף המכוון.

כעת, יהא \( r \) אינדקס של צומת כלשהו בגרף, ונסמן ב-\( L^{\left(r\right)} \) את מטריצת המינור ה-\( r \)-ית של \( L \) - המטריצה שמתקבלת מ-\( L \) על ידי מחיקת השורה והעמודה ה-\( r \)-יות. אז הנה משפט קירכהוף, בגרסה שנכונה הן לגרפים מכוונים והן לגרפים לא מכוונים:

מספר העצים הפורשים של הגרף \( G \) שהשורש שלהם הוא \( v_{r} \) הוא \( \det L^{\left(r\right)} \).

(בגרף לא מכוון אין ממש משמעות ל”שורש” ולכן כדי למצוא את מספר העצים הפורשים אפשר לבחור \( r \) שרירותי; בגרף מכוון שורש הוא הצומת היחיד בעץ שקיים מסלול ממנו אל שאר הצמתים בגרף).

שימו לב שעניין המינור הכרחי: לא קשה לראות ש-\( \det L=0 \) תמיד כי סכום כל עמודה במטריצה הוא 0 ולכן שורות המטריצה תלויות לינארית. כמובן ש-\( L \) מעניינת גם לכשעצמה - למשל, יש חשיבות גדולה לערך העצמי הבא החיובי הקטן ביותר שלה; אבל לא אכנס לכל זה כרגע.

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

את קושי-בינה לא רואים בדרך כלל בקורס בסיסי באלגברה לינארית וקצת חבל. יש לה גם הוכחה קומבינטורית יפהפיה משל עצמה (גם היא ב-Proofs from THE BOOK) שלא אציג כרגע. בבסיסה, הנוסחה היא הכללה של נוסחה בסיסית שכן רואים באלגברה לינארית: אם \( A,B \) הן מטריצות ריבועיות, אז \( \det\left(A\cdot B\right)=\det A\cdot\det B \).

העניין הוא בכך שמטריצות ריבועיות עשויות להתקבל גם כמכפלה של מטריצות לא ריבועיות: אם \( A \) היא מטריצה \( n\times m \) ו-\( B \) היא מטריצה \( m\times n \) אז מכפלתם \( AB \) היא מטריצה \( n\times n \), ולכן אפשר לדבר על הדטרמיננטה שלה. מצד שני, \( A,B \) אינן ריבועיות ולכן אין משמעות לדטרמינטטה שלהן. האם בכל זאת אפשר לעשות משהו?

אם \( m<n \) אין על מה לדבר, אבל רק כי אז מובן מאליו ש-\( \det AB=0 \). למה מובן מאליו? ובכן, זה תרגיל טוב באלגברה לינארית: אם \( m<n \) אז דרגת \( A,B \) היא לכל היותר \( m \) כל אחד; ולכן דרגת המכפלה \( AB \) גם היא לכל היותר \( m \), ולכן \( AB \) היא מטריצה מדרגה לא מלאה ובהכרח הדטרמיננטה שלה היא 0.

מצד שני, אם \( m>n \), נוסחת קושי בינה נכנסת לפעולה. במילים מה שהולך כאן הוא הדבר הבא: \( A \) היא מטריצה מלבנית, אבל היא מכילה הרבה תת-מטריצות ריבועיות \( n\times n \), שמתקבלות מבחירת תת-קבוצה של \( n \) מתוך \( m \) העמודות שלה. באותו האופן גם \( B \) מכילה הרבה תת-מטריצות ריבועיות \( n\times n \) שמתקבלות מבחירת תת-קבוצה של \( n \) מתוך \( m \) השורות שלה. אם נסמן ב-\( \sigma \) בחירה מסויימת של \( n \) מתוך \( m \) אינדקסים, אז נוסחת קושי-בינה היא פשוט \( \det\left(AB\right)=\sum_{\sigma}\left(\det A_{\sigma}\cdot\det B_{\sigma}\right) \). כלומר: לכל בחירה אפשרית של \( n \) מתוך \( m \) אינדקסים \( \sigma \) ניקח מתוך \( A \) ו-\( B \) את תת המטריצות המתאימות (שימו לב שזו אותה בחירת אינדקסים לשתי המטריצות! זה מה שחשוב פה), נחשב את מכפלת הדטרמיננטות שלהן, ונסכום את הכל (אם \( m<n \) אז אפשר להסכים על כך שהסכום ריק ולכן שווה 0, ובכך לקבל נוסחה שתקפה לכל מקרה אפשרי).

איך נוסחת קושי-בינה מסייעת לנו כאן? ובכן, את הלפלסיאן קל למדי לכתוב כמכפלה של מטריצות. בואו נדבר לבינתיים על המקרה של גרף לא מכוון שהוא פשוט קצת יותר, ונגדיר מטריצה \( A \) - “מטריצת החילה” (Incidence matrix) של הגרף. זו תהיה מטריצה \( n\times m \) שבה כל שורה מייצגת צומת בגרף וכל עמודה מייצגת קשת בגרף, כך שלכל קשת \( e_{k}=\left(v_{i},v_{j}\right) \) עם \( i<j \) נקבע ש-\( A_{ik}=1,A_{jk}=-1 \) וכל כניסה אחרת במטריצה היא 0. במילים אחרות, כל עמודה במטריצה הזו מכילה בדיוק 1 בודד ו-\( -1 \) בודד, בשני הצמתים שמתאימים לקשת של אותה עמודה.

כעת זה תרגיל נחמד לבדוק שאכן \( L=A\cdot A^{T} \) (כאן \( A^{T} \) מייצג את השחלוף של \( A \): \( A_{ij}^{T}=A_{ji} \)). ומהו \( L^{\left(r\right)} \)? לא קשה לראות שהוא \( NN^{T} \) כאשר \( N \) מתקבלת מ-\( A \) על ידי מחיקת השורה ה-\( r \). שימו לב שאנחנו לא מוחקים מ-\( A \) עמודות; הקשתות שהיו מחוברות ל-\( v_{r} \) עדיין מיוצגות ב-\( N \), אבל באופן “חלקי” - העמודה שלהן מכילה רק 1 או רק \( -1 \). זו אולי הנקודה הקריטית ביותר בהמשך ההוכחה.

עכשיו, על פי קושי-בינה, \( \det\left(L^{\left(r\right)}\right)=\sum_{\sigma}\det N_{\sigma}\det N_{\sigma}^{T}=\sum_{\sigma}\det\left(N_{\sigma}\right)^{2} \). הצטמצמנו להבנה של מהו \( \det\left(N_{\sigma}\right) \) לכל בחירה מתאימה של עמודות. שימו לב של-\( N \) יש \( n-1 \) שורות (כי בגרף המקורי היו \( n \) צמתים והסרנו את השורה של הצומת \( v_{r} \) מהמטריצה \( A \) כדי לקבל את \( N \)), ולכן כל \( \sigma \) היא בחירה של \( n-1 \) עמודות, כלומר של \( n-1 \) קשתות מהגרף המקורי. והנה לב ההוכחה, התובנה המרכזית בה, מה שהופך את הכל לברור לדעתי: אותה בחירה \( \sigma \) של \( n-1 \) עמודות היא בדיקה שלנו האם מועמד כלשהו לתפקיד עץ פורש הוא אכן עץ פורש. הדטרמיננטה \( \det N_{\sigma} \) תהיה בדיוק אבן הבוחן: אם \( \sigma \) אכן מהווה בחירה של \( n-1 \) קשתות שיוצרות עץ פורש, נקבל ש-\( \det N_{\sigma}=\pm1 \); ואחרת נקבל \( \det N_{\sigma}=0 \). זה בבירור מסיים את ההוכחה שכן אז נקבל ש-\( \sum_{\sigma}\det\left(N_{\sigma}\right)^{2} \) הוא בדיוק מספר ה-\( \sigma \)-ות שעבורן קיבלנו עץ פורש, כלומר מספר העצים הפורשים של הגרף.

אתם עוד איתי? אם כן, הבנתם את ההוכחה; נותר לגהץ את הפרטים.

נתחיל במקרה שבו \( \sigma \) לא מגדירה עץ פורש בגרף \( G \). אנחנו רוצים להראות ש-\( \det N_{\sigma}=0 \) במקרה הזה, ונעשה זאת על ידי כך שנוכיח שבמטריצה \( N_{\sigma} \) יש קבוצה של שורות שסכומן אפס. תוצאה בסיסית על עצים היא שאם גרף לא מכוון עם \( n \) צמתים ו-\( n-1 \) קשתות הוא גם קשיר, אז הוא עץ; לכן אם \( \sigma \) אינה משרה עץ בהכרח יש שני רכיבי קשירות. \( v_{r} \) נמצא באחד מהם; בואו נסתכל דווקא על השני - וליתר דיוק, על השורות במטריצה \( N_{\sigma} \) שמתאימות לצמתים של אותו רכיב קשירות שני. אני טוען שסכום כל השורות הללו הוא 0. מדוע? ובכן, נעבור עמודה עמודה: כל עמודה מתאימה לקשת שמחברת שני צמתים. אם שניהם אינם ברכיב הקשירות ממילא, אז בשורות שמתאימות לרכיב הקשירות כל הכניסות בעמודה הזו יהיו 0. אם שניהם ברכיב הקשירות, אז תהיה שורה שבה יופיע 1, ושורה שבה יופיע \( -1 \), ובשאר השורות 0 - ושוב, הסכום הוא 0. ואם אחד מהצמתים ברכיב הקשירות והשני לא? ובכן, זה בלתי אפשרי כי זה נוגד את ההגדרה של רכיב קשירות: אם צומת נמצא ברכיב קשירות מסויים, כך גם כל שכניו.

הטיעון הטכני ביותר יהיה ההוכחה ש-\( \det N_{\sigma}=\pm1 \) כאשר \( \sigma \) כן מתאימה לעץ פורש, אבל אחר כך סיימנו את ההוכחה כולה. הרעיון הוא שבמקרה הזה, אפשר לסדר מחדש את שורות ועמודות \( N_{\sigma} \) כך שתתקבל מטריצה משולשית תחתונה (מטריצה שבה כל הכניסות מעל לאלכסון הראשי הן 0), ואת הדטרמיננטה של מטריצה משולשית קל לחשב - זו בסך הכל מכפלת האיברים שעל האלכסון. מכיוון שסידור מחדש של שורות או עמודות משנה רק את הסימן של הדטרמיננטה, זה יסיים את ההוכחה. את המטריצה המסודרת-מחדש אסמן ב-\( M \).

אמרנו ש-\( \sigma \) מהווה עץ. מה שנעשה הוא להתחיל לפרק את העץ לגורמים. ראשית, בואו נזכור שעלה בעץ הוא צומת מדרגה 1, כלומר שמחובר בדיוק לצומת אחר אחד. עוד משפט חשוב על עצים הוא שבעץ יש לפחות שני עלים; לא אוכיח אותו כרגע.

הבה ונסמן ב-\( u_{1} \) עלה שכזה שהוא שונה מ-\( v_{r} \) (תמיד יש כזה; אפילו אם \( v_{r} \) הוא עלה, יש עוד עלה שאפשר לבחור) וב-\( e_{1} \) את הקשת בעץ שמחוברת אליו. השורה הראשונה במטריצה-המסודרת-מחדש שלנו תהיה זו של \( u_{1} \), והעמודה הראשונה תהיה זו של \( e_{1} \). מכיוון ש-\( u_{1} \) מחובר רק ל-\( e_{1} \) בעץ, הכניסה \( M_{11} \) תהיה שווה ל-1 או ל-\( -1 \)(לא משנה לנו איזה מהם), וכמו כן \( M_{1j}=0 \) לכל \( j>1 \) (ובכלל לא משנה איך אני הולך לסדר את יתר העמודות), שכן כל העמודות הללו מתאימות לקשתות ש-\( u_{1} \) לא מחובר אליהן.

כעת נסיר את \( u_{1} \) מהעץ שלנו (ויחד איתו את \( e_{1} \)), ושוב נקבל עץ, ולכן שוב יש בו צומת מדרגה 1 שאינו \( v_{r} \). זה יהיה \( u_{2} \) והקשת שמתאימה לו תהיה \( e_{2} \). זה אומר ש-\( M_{22} \) הוא שוה \( \pm1 \); ואנו יודעים בודאות שעבור הקשתות שטרם טיפלנו בהן, \( u_{2} \) אינו מחובר לאף אחת מהן ולכן \( M_{2j}=0 \) לכל \( j>2 \) (אולי הוא היה מחובר ל-\( e_{1} \), אבל זה אומר רק שאולי \( M_{12}\ne0 \) וזה לא מפריע לנו כי כניסה זו היא מתחת לאלכסון הראשי). העיקרון ברור - נמשיך לבנות כך סדרה \( u_{1},u_{2},\dots,u_{n-1} \) של צמתים ו-\( e_{1},e_{2},\dots,e_{n-1} \) של קשתות. הצומת היחיד שלא נגענו בו הוא \( v_{r} \) עצמו, שהשורה שמתאימה לו בכלל לא מופיעה ב-\( N \) כך שהוא לא רלוונטי לבניה שעשינו. קיבלנו מטריצה משולשת תחתונה שעל האלכסון יש לה רק \( \pm1 \) וזה מסיים את ההוכחה.

אני מאוד מקווה שנהניתם מההוכחה הזו כפי שאני נהניתי ממנה.

בואו נעבור עכשיו לדבר על מה צריך להשתנות בהוכחה אם נרצה להוכיח את המשפט לגרפים מכוונים. כבר אמרתי שצריך לשנות את הגדרת מטריצת הלפלסיאן עצמה קצת: \( L_{ii} \) הוא דרגת הכניסה של כל צומת ו-\( L_{ij} \) הוא מינוס מספר הקשתות מ-\( v_{i} \) אל \( v_{j} \). זו לא מטריצה סימטרית ולכן גם לא בהכרח ניתן לכתוב אותה בתור \( A\cdot A^{T} \); אבל אפשר לעשות משהו טוב כמעט באותה מידה.

הבה ונגדיר שוב מטריצה \( A \) מסדר \( n\times m \) (כלומר - שורה לכל צומת ועמודה לכל קשת, כמקודם) באופן הבא: לכל קשת \( e_{k}=v_{i}\to v_{j} \) (כלומר, מהצומת \( v_{i} \) אל הצומת \( v_{j} \)) יתקיים \( A_{ik}=1,A_{jk}=-1 \) ושאר הכניסות יהיו אפס; במילים אחרות, זו בדיוק אותה מטריצה \( A \) כמו קודם רק שעכשיו אנחנו קובעים איזו כניסה תהיה חיובית ואיזו כניסה תהיה שלילית על פי כיוון הקשת \( e_{k} \).

בנוסף, נגדיר מטריצה \( B \) מסדר \( n\times m \) באופן הבא: לכל קשת \( e_{k}=v_{i}\to v_{j} \) יתקיים \( B_{ik}=0,B_{jk}=-1 \) ושאר הכניסות יהיו אפס. כלומר, \( B \) זהה ל-\( A \) פרט לכך שבכל עמודה יש רק \( -1 \) עבור הצומת שאליו הקשת נכנסת; לא מופיע 1 עבור הצומת שממנו הקשת יוצאת.

עכשיו לא קשה לראות ש-\( L=A\cdot B^{T} \) וש-\( L^{\left(r\right)} \) הוא \( N_{A}N_{B}^{T} \) כאשר \( N_{A},N_{B} \) מתקבלים מ-\( A,B \) בהתאמה על ידי מחיקת השורה ה-\( r \). אז קושי-בינה מניבה פה \( \det\left(L^{\left(r\right)}\right)=\sum_{\sigma}\det\left(N_{A\sigma}\right)\det\left(N_{B\sigma}\right) \). עכשיו צריך להבין מה קורה פה.

היינו רוצים לומר שאם \( \sigma \) לא מגדיר עץ, אז נקבל ש-\( \det\left(N_{A\sigma}\right)=0 \) בדיוק כמו קודם ואז גם המכפלה תתאפס. לרוע המזל, “\( \sigma \) לא מגדיר עץ” הוא מקרה הרבה יותר מסובך כאשר הגרף שלנו מכוון, כי הקריטריון של “גרף עם \( n-1 \) קשתות שהוא קשיר הוא עץ” פשוט לא נכון. בעץ מכוון, צריך שיהיה צומת (השורש) שקיים מסלול ממנו לכל הצמתים האחרים, ומספיקה קשת אחת בכיוון הלא נכון כדי לקלקל את זה. לכן בואו נתחיל קודם כל דווקא מדיבור על המקרה שבו \( \sigma \) כן מגדיר עץ. מה נשתנה הפעם?

ובכן, הפעם צריכים להיות קצת יותר זהירים בגלל ש-\( \det\left(N_{A\sigma}\right)\det\left(N_{B\sigma}\right) \) הוא לא ריבוע. מה שאנחנו רוצים לטעון הוא שמתקיים \( \det\left(N_{A\sigma}\right)=\det\left(N_{B\sigma}\right) \) וששניהם שווים או 1 או \( -1 \). אפשר להשתמש בשיטת הסידור-מחדש של מטריצה כמו קודם; רק צריך להיות זהירים ולסדר את \( N_{A\sigma} \) ואת \( N_{B\sigma} \) באותו האופן בדיוק כדי שהשינוי בסימן, אם היה כזה, יהיה זהה אצל שניהם.

אחרי הסידור מחדש של המטריצה, מה שמתקבל מ-\( N_{A\sigma} \) ומ-\( N_{B\sigma} \) היא כמקודם מטריצה משולשית תחתונה, אבל מה נמצא על האלכסון? כאן האופן שבו ביצענו את הסדר הופך להיות קריטי: להזכירכם, בשיטה שלנו בשלב ה-\( i \) קבענו את השורה ה-\( i \) להיות צומת \( u_{i} \) שבשלב הזה היה עלה, ואת העמודה להיות קשת \( e_{i} \) שהיא הקשת שנכנסת אל \( u_{i} \). כלומר, הן על פי ההגדרה של \( A \) והן על פי ההגדרה של \( B \), הכניסה המתאימה תהיה \( -1 \). זה מבטיח שהדטרמיננטה תהיה מכפלה של \( -1 \)-ים ושלא ישתרבב פנימה איזה 0 שיאפס את כולה (מה שהיה עלול לקרות עם \( B \), שבו יש אפסים שלא היו בהוכחה עבור גרפים לא מכוונים).

עכשיו נחזור למקרה שבו \( \sigma \) הוא לא עץ. מי שיושיע אותנו כאן הוא שאנחנו משתמשים גם ב-\( N_{A\sigma} \) וגם ב-\( N_{B\sigma} \): הדטרמיננטה של אחד מהם תתאפס, ולא משנה מה. התעלול פשוט: אם \( \sigma \) הוא כזה שאפילו גרף התשתית של העץ שלנו (מה שמקבלים כשמוחקים את כיווני הקשתות) איננו עץ אז \( \det\left(N_{A\sigma}\right)=0 \) מאותו שיקול כמו במקרה הלא מכוון (סכום שורות שהוא אפס, מה שמובטח על ידי ה-1 וה-\( -1 \) שיש בכל עמודה שם - וזה משהו שאין ב-\( B \)), ואילו אם גרף התשתית הוא כן עץ, אז נסדר מחדש את \( N_{B\sigma} \) על פי אותה שיטה שבה השתמשנו עד כה במקרים שבהם \( \sigma \) הגדיר עץ. נקבל מטריצה משולשית תחתונה כמו תמיד, רק שהפעם אחד מהאיברים על האלכסון יהיה 0. מדוע? כי אם \( \sigma \) איננו עץ למרות שגרף התשתית הוא כן עץ, זה אומר שיש קשת אחת שמכוונת בכיוון “הלא נכון”, ואז הכניסה על האלכסון שמתאימה לקשת הזו ולצומת שמחוברת אליה תהיה 0 (כי הקשת יוצאת מהצומת במקום להיכנס אליו).

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