שינויים
{{left|<math>\underbrace\begin{pmatrix}1&1&1&0\\1&1&0&0\\0&0&0&1\\1&0&1&0\end{pmatrix}_\mathbf A\underbrace\begin{pmatrix}A\\B\\C\\D\end{pmatrix}_\mathbf x=\underbrace\begin{pmatrix}1\\0\\1\\1\end{pmatrix}_\mathbf b</math>}}
הצגה זו מאפשרת לנו למצוא מה הסוג של כל תושב ע״י פתרון מערכת משוואות לינאריות. יתרה מזאת, לפי משפט רושה–קפלי (Rouché–Capelli) יש פתרון ל־<math>\mathbf{Ax}=\mathbf b</math> אם״ם <math>\mathbf b\in\operatorname{span}\left\{\operatorname{Col}_i(\mathbf A)\right\}_{i=1}^n</math> כאשר <math>\operatorname{Col}_i(\mathbf A)</math> העמודה ה־<math>i</math> של <math>\mathbf A</math>, ואם כן אז מרחב הפתרונות הוא ממימד <math>n-\operatorname{rank}(\mathbf A)</math>. מכאן נובע שאנו יכולים לבדוק האם קיים פתרון לחידה, ואם כן לחשב את מספר הפתרונות בתור <math>2^{n-\operatorname{rank}(\mathbf A)}</math>. מובן שבד״כ יש רק פתרון אחד, כלומר <math>\operatorname{rank}(\mathbf A)=n</math> ואז, אם ל־<math>\mathbf A</math> יש <math>n</math> שורות אז היא הפיכה. אם לא אז ניתן למחוק כמה שורות של <math>\mathbf A</math> (וגם את השורות המתאימות ב־<math>\mathbf b</math>) כך שהיא תהיה הפיכה.
:'''דוגמה 1.3:''' נפתור את ''דוגמה 1''. חישוב פשוט מראה ש־<math>\mathbf A</math> הפיכה (ומכאן שיש פתרון יחיד) ו־<math>\mathbf A^{-1}=\begin{pmatrix}1&1&0&1\\1&0&0&1\\1&1&0&0\\0&0&1&0\end{pmatrix}</math>. לכן <math>\mathbf x=\mathbf A^{-1}\mathbf b=\begin{pmatrix}0\\0\\1\\1\end{pmatrix}</math> – התושבים <math>A,B</math> נוכלים ו־<math>C,D</math> אבירים.
כדי לפתור את החידה נבחר <math>\mathbf Q\in\{0,1\}^{k\times n}</math> כך ש־<math>\begin{pmatrix}\mathbf A\\\mathbf Q\end{pmatrix}</math> מטריצה הפיכה, ואז <math>\mathbf q=\mathbf Q\mathbf x</math> ו־<math>\mathbf x=\begin{pmatrix}\mathbf A\\\mathbf Q\end{pmatrix}^{-1}\begin{pmatrix}\mathbf b\\\mathbf r\end{pmatrix}</math>. לשם כך צריך להראות שקיימת <math>\mathbf Q</math> כנ״ל, אבל זה די טריוויאלי: השורות של <math>\mathbf A</math> בת״ל ולכן הן בסיס לתת־מרחב של <math>\{0,1\}^{1\times n}</math> ממימד <math>k</math>. נבחר בסיס כלשהו ל[http://en.wikipedia.org/wiki/Orthogonal_complement תת־מרחב המשלים האורתוגונלי] לו ונציב את איבריו כשורות מטריצה <math>\mathbf Q</math>. אזי <math>\begin{pmatrix}\mathbf A\\\mathbf Q\end{pmatrix}\in\{0,1\}^{(n-k+k)\times n}=\{0,1\}^{n\times n}</math> מטריצה ריבועית ששורותיה בת״ל, כלומר היא הפיכה. {{משל}}
:'''דוגמה 4.2:''' עלינו למצוא את הסוגים של כל התושבים בדוגמה 5 במינימום שאלות, כלומר ב־<math>k=n-\operatorname{rank}(\mathbf A)=2</math> שאלות(הוכחה ש־<math>k</math> הוא המספר המינימלי הדרוש של שאלות – בהמשך). שני וקטורי שורה שאינם תלויים לינארית ב־<math>\begin{pmatrix}1&1&1&0\end{pmatrix},\begin{pmatrix}1&1&0&0\end{pmatrix}</math> הם לדוגמה <math>\begin{pmatrix}0&0&0&1\end{pmatrix},\begin{pmatrix}1&0&1&0\end{pmatrix}</math> ולכן <math>\mathbf q=\begin{pmatrix}X_4\\X_1\nleftrightarrow X_3\end{pmatrix}</math> וקטור שאלות מתאים. <math>\begin{pmatrix}\mathbf A\\\mathbf Q\end{pmatrix}^{-1}=\begin{pmatrix}1&1&1&0\\1&1&0&0\\0&0&0&1\\1&0&1&0\end{pmatrix}^{-1}=\begin{pmatrix}1&1&0&1\\1&0&0&1\\1&1&0&0\\0&0&1&0\end{pmatrix}</math> והפתרון הכללי הוא <math>\mathbf x=\begin{pmatrix}1&1&0&1\\1&0&0&1\\1&1&0&0\\0&0&1&0\end{pmatrix}\begin{pmatrix}1\\0\\\mathbf r\!\!\!\!\!\begin{matrix}&\\&\end{matrix}\end{pmatrix}</math>.
==== המספר המינימלי של שאלות ====
נניח ש־<math>m</math> הוא המספר המינימלי של שאלות הדרוש לפתרון חידת שאלות נתונה ונרצה להוכיח ש־<math>m=k=\lceil\log_2(|S|)\rceil</math>: תהי <math>V=\{\mathbf x:\ \mathbf A\mathbf x=\mathbf 0\}</math> כך ש־<math>\mathbf A\in\{0,1\}^{(n-k)\times n}</math> מטריצה כרצוננו ששורותיה בת״ל. לכן <math>|V|=2^{n-\operatorname{rank}(\mathbf A)}=2^k</math> ובפרט קיימת פונקציה <math>f:S\to V</math> חח״ע. תהי <math>\mathbf Q\in\{0,1\}^{k\times n}</math> מטריצה כך ש־<math>\begin{pmatrix}\mathbf A\\\mathbf Q\end{pmatrix}</math> הפיכה ואז <math>\mathbf q':\mathbf v\mapsto\mathbf Q\mathbf v</math> חח״ע מ־<math>V</math>. נגדיר <math>\mathbf q=f^{-1}\circ\mathbf q'\circ f</math> ולכן <math>\mathbf q</math> חח״ע מ־<math>S</math> והיא מורכבת מ־<math>k</math> שאלות, כלומר <math>k\ge m</math>. בעבר הוכחנו ש־<math>k\le m</math> ולכן <math>m=k</math>. {{משל}}
