שינויים
כדי לפתור את החידה נבחר <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 4 במינימום שאלות, כלומר ב־<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=\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>. {{משל}}
