document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=1201735>Question 1201735</A>: <I><SPAN STYLE=\"word-break: break-all;\"> Let X be the design matrix of a linear regression problem with m rows (samples) and d columns (variables/features). Let y∈R^m be the response vector corresponding the samples in X. Recall that for some vector space V⊆R^d the orthogonal complement of V is: V^⊥:={x∈R^d∣⟨x,v⟩=0∀v∈V} \r<BR>\n" );
document.write( "\n" );
document.write( "1. Prove that: Ker(X)=Ker(X^⊤X) \r<BR>\n" );
document.write( "\n" );
document.write( "2. Prove that for a square matrix A:Im(A^⊤)=Ker(A)^⊥<BR>\n" );
document.write( "  <BR>\n" );
document.write( "3. Let y=Xw be a non-homogeneous system of linear equations. Assume that X is square and not invertible. Show that the system has ∞ solutions ⇔y⊥Ker(X^⊤). \r<BR>\n" );
document.write( "\n" );
document.write( "4. Consider the (normal) linear system X^⊤Xw=X^⊤y. Using what you have proved above prove that the normal equations can only have a unique solution (if X^⊤X is invertible) or infinitely many solutions (otherwise).\r<BR>\n" );
document.write( "\n" );
document.write( "Please help me to solve question 3 and 4. </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #848017 by </B><A HREF=/tutors/aboutme.mpl?userid=asinus><B>asinus(45)</B></A><img src=\"/images/stars/stars-07.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=asinus><IMG SRC=http://www.algebra.com/images/aboutme-small.gif BORDER=0 alt=\"About Me\" VALIGN=MIDDLE></A>&nbsp;<IMG SRC=http://www.algebra.com/images/nopicture.jpg><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=848017\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> Let's tackle each part of the problem step by step.\r<BR>\n" );
document.write( "\n" );
document.write( "### 1. Prove that $ \text{Ker}(X) = \text{Ker}(X^TX) $\r<BR>\n" );
document.write( "\n" );
document.write( "**Proof:**\r<BR>\n" );
document.write( "\n" );
document.write( "- Let $ v \in \text{Ker}(X) $. Then, by definition, $ Xv = 0 $.<BR>\n" );
document.write( "- Multiplying both sides by $ X^T $, we have:<BR>\n" );
document.write( "  $$<BR>\n" );
document.write( "  X^TXv = X^T0 = 0<BR>\n" );
document.write( "  $$<BR>\n" );
document.write( "  Thus, $ v \in \text{Ker}(X^TX) $.\r<BR>\n" );
document.write( "\n" );
document.write( "- Now, let $ v \in \text{Ker}(X^TX) $. Then $ X^TXv = 0 $.<BR>\n" );
document.write( "- This implies $ \langle Xv, Xv \rangle = 0 $ (since $ \langle a, a \rangle = 0 $ if and only if $ a = 0 $).<BR>\n" );
document.write( "- Therefore, $ Xv = 0 $, which means $ v \in \text{Ker}(X) $.\r<BR>\n" );
document.write( "\n" );
document.write( "Combining both parts, we conclude:<BR>\n" );
document.write( "$$<BR>\n" );
document.write( "\text{Ker}(X) = \text{Ker}(X^TX)<BR>\n" );
document.write( "$$\r<BR>\n" );
document.write( "\n" );
document.write( "### 2. Prove that for a square matrix $ A $: $ \text{Im}(A^T) = \text{Ker}(A)^\perp $\r<BR>\n" );
document.write( "\n" );
document.write( "**Proof:**\r<BR>\n" );
document.write( "\n" );
document.write( "- Let $ v \in \text{Im}(A^T) $. Then there exists some $ u $ such that $ v = A^Tu $.<BR>\n" );
document.write( "- For any $ w \in \text{Ker}(A) $, we have $ Aw = 0 $.<BR>\n" );
document.write( "- Thus, $ \langle v, w \rangle = \langle A^Tu, w \rangle = \langle u, Aw \rangle = \langle u, 0 \rangle = 0 $.<BR>\n" );
document.write( "- This shows that $ v \in \text{Ker}(A)^\perp $.\r<BR>\n" );
document.write( "\n" );
document.write( "- Now, let $ v \in \text{Ker}(A)^\perp $. We need to show $ v \in \text{Im}(A^T) $.<BR>\n" );
document.write( "- By the definition of orthogonal complement, $ \langle v, w \rangle = 0 $ for all $ w \in \text{Ker}(A) $.<BR>\n" );
document.write( "- The rank-nullity theorem states that $ \text{dim}(\text{Im}(A)) + \text{dim}(\text{Ker}(A)) = d $.<BR>\n" );
document.write( "- Since $ A $ is square, $ \text{Im}(A^T) $ has dimension equal to $ \text{dim}(\text{Ker}(A)) $.<BR>\n" );
document.write( "- Therefore, $ \text{Im}(A^T) = \text{Ker}(A)^\perp $.\r<BR>\n" );
document.write( "\n" );
document.write( "### 3. Show that the system $ y = Xw $ has $ \infty $ solutions $ \Leftrightarrow y \perp \text{Ker}(X^T) $\r<BR>\n" );
document.write( "\n" );
document.write( "**Proof:**\r<BR>\n" );
document.write( "\n" );
document.write( "- If $ y \perp \text{Ker}(X^T) $, then for any $ v \in \text{Ker}(X^T) $, we have $ \langle y, v \rangle = 0 $.<BR>\n" );
document.write( "- This means that $ y $ can be expressed as $ y = Xw + v $ for some $ w $ and $ v \in \text{Ker}(X^T) $.<BR>\n" );
document.write( "- Since $ v $ can take infinitely many values in $ \text{Ker}(X^T) $, there are infinitely many $ w $ that satisfy $ y = Xw $.\r<BR>\n" );
document.write( "\n" );
document.write( "- Conversely, if the system has infinitely many solutions, then there exists a non-zero $ v \in \text{Ker}(X^T) $ such that $ y = Xw + v $.<BR>\n" );
document.write( "- This implies $ y \perp \text{Ker}(X^T) $.\r<BR>\n" );
document.write( "\n" );
document.write( "Thus, we conclude:<BR>\n" );
document.write( "$$<BR>\n" );
document.write( "y \perp \text{Ker}(X^T) \Leftrightarrow \text{the system has } \infty \text{ solutions}<BR>\n" );
document.write( "$$\r<BR>\n" );
document.write( "\n" );
document.write( "### 4. Prove that the normal equations $ X^TXw = X^Ty $ can only have a unique solution (if $ X^TX $ is invertible) or infinitely many solutions (otherwise)\r<BR>\n" );
document.write( "\n" );
document.write( "**Proof:**\r<BR>\n" );
document.write( "\n" );
document.write( "- If $ X^TX $ is invertible, then the normal equations have a unique solution given by:<BR>\n" );
document.write( "  $$<BR>\n" );
document.write( "  w = (X^TX)^{-1}X^Ty<BR>\n" );
document.write( "  $$\r<BR>\n" );
document.write( "\n" );
document.write( "- If $ X^TX $ is not invertible, then $ \text{Ker}(X^TX) \neq \{0\} $. From part 1, we know:<BR>\n" );
document.write( "  $$<BR>\n" );
document.write( "  \text{Ker}(X^TX) = \text{Ker}(X)<BR>\n" );
document.write( "  $$<BR>\n" );
document.write( "- If $ y \perp \text{Ker}(X^T) $, then the system has infinitely many solutions, as shown in part 3.\r<BR>\n" );
document.write( "\n" );
document.write( "Thus, we conclude:<BR>\n" );
document.write( "- The normal equations have a unique solution if $ X^TX $ is invertible.<BR>\n" );
document.write( "- They have infinitely many solutions if $ X^TX $ is not invertible.\r<BR>\n" );
document.write( "\n" );
document.write( "This completes the proof for all parts. </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );