\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage[table]{xcolor}
\usepackage[all,arc]{xy}
\usepackage{color, colortbl}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.15in}
\setlength{\evensidemargin}{.15in}
\setlength{\textwidth}{6.2in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{8.6in}


\input{preamble.tex}

\begin{document}

\homework{2: Linear Algebra and More Circuits}{Due Friday, Week 2}

Do \textbf{three} of the following \textbf{five} problems!

\begin{enumerate}
\item 
\begin{enumerate}
\item Prove the following ``basis-trading lemma:''
\begin{lem}
Suppose that $V$ is a vector space, and that $B = \{\vec{v}_1, \vec{v}_2, \ldots \vec{v}_m\}$, $C = \{\vec{w}_1, \vec{w}_2, \ldots \vec{w}_n\}$ are a pair of finite bases for $V$.  Take any $\vec{v_i} \in B$.  Then there is some $\vec{w}_j \in C$ such that the set
\begin{align*}
D = (C \cup \{\vec{v}_i\}) \setminus \{\vec{w}_j\}
\end{align*} 
formed by ``replacing'' $\vec{w}_j$ with $\vec{v}_i$ is a basis.
\end{lem}
\item Using (a), prove the following claim:\ if $V$ is a vector space and $B, C$ are two different bases for $V$, then $|B| = |C|$.
\end{enumerate} 
\item Using the Axiom of Choice, extend (1) above to infinite bases:\ that is, show that if $V$ is a vector space and $B, C$ are a pair of infinite bases for $V$, then $|B| = |C|$.

\item A basis for $\mathbb{R}^n$ is called a \textbf{Hadamard basis} if it satisfies the following two properties:
\begin{enumerate}
\item[$\star.$] Every vector in the basis is made up out of entries from $\pm 1$.
\item[$\ddag.$] The dot product of any two vectors in the basis is 0.
\end{enumerate}

For example, $\{(1,1), (1,-1)\}$ is such a basis for $\mathbb{R}^2$.
\begin{enumerate}
\item Find such a basis for $\mathbb{R}^4$.
\item Show that no such basis exists for $\mathbb{R}^7$.
\item Show that such a basis exists for $\mathbb{R}^n$, whenever $n$ is a power of 2.
\end{enumerate}



\item  Prove the following claims about resistors:
\begin{enumerate}
\item The effective resistance of the circuit below is the reciprocal of the sum of the reciprocals of the resistors in the circuit.  In other words, the circuit
\begin{center}
\includegraphics[width=3in]{resistors_parallel.pdf}
\end{center}
has effective resistance given by the formula
\begin{align*}
\frac{1}{R_{\textrm{eff}}} = \sum_{i=1}^n \frac{1}{R_i}.
\end{align*}
\item 
The effective resistance of the circuit below is the sum of the resistors in the circuit.  In other words, the circuit
\begin{center}
\includegraphics[width=3.5in]{resistors_series.pdf}
\end{center}
has effective resistance given by the formula
\begin{align*}
R_{\textrm{eff}} = \sum_{i=1}^n R_i.
\end{align*}


\end{enumerate}
\item Take an arbitrary circuit.  Define the \textbf{star-triangle} transformation as follows:
\begin{center}
\includegraphics[width=3in]{math137b_s2014_midtermcirc.pdf}\\
\footnotesize The star-triangle transformation.  In the above diagram, $S = R_1R_2 + R_1R_3 + R_2R_3$. \normalsize
\end{center}
This process takes a $Y$-configuration of resistors with resistances $R_1, R_2, R_3$ as labeled above, and replaces it with a $\Delta$-configuration of resistors with resistances $S/R_1, S/R_2, S/R_3$ as labeled above, with $S = R_1R_2 + R_1R_3 + R_2R_3$.  

Prove that this replacement does not change the overall resistance of the circuit in which it is performed.




\item[(Bonus!)]  Show that there is a Hadamard basis for $\mathbb{R}^{n}$ whenever $n$ is a multiple of 4. (Warning: harder.)

\end{enumerate}



\end{document}