I am reading "Interlacing Eigenvalues and Graphs" by Willem H. Haemers. Right at the start in the proof of theorem 2.1 there is a step (marked in a red box below) which I do not understand. My knowledge of linear algebra is not good enough.
..
What do we know?
- $m < n$
- $u_1, ..., u_n$ are the orthonormal basis in $\mathbb R^n$ of symmetric martix $A$
- $S \in \mathbb R^{n,m}$ and $S^\intercal \in \mathbb R^{m,n}$
- Since $S^\intercal \circ S = I_m$, it follows that $S$ has rank $m$ and the column vectors $y_1,...,y_m \in \mathbb R^n$ of $S$ are an orthonormal system.
- The matrix $S \circ S^\intercal \in \mathbb R^{n,n}$ is an orthogonal projector via $S \circ S^\intercal = \sum_{\ell = 1}^m y_\ell\circ y_\ell^\intercal$.
- There is a vector $s_i \in \mathbb R^m\setminus \{0\}$ with $s_i \in \left\langle S^\intercal \circ u_1,...,S^\intercal \circ u_{i-1}\right\rangle^\perp$.
Question: Why do these properties imply that $S \circ s_i \in \left\langle u_1,..., u_{i-1}\right\rangle^\perp$.
Note that there is a typo in the red box above: $u_{n-1}$ is wrong but $u_{i-1}$ is correct.
Thank you for your thoughts!
If $\ s_i \in \langle S^\intercal u_1, \dots, S^\intercal u_{i-1}\rangle^\perp\ $ then $\ s_i^\intercal S^\intercal u_j = 0\ $ for $\ j=1,2,\dots,i-1\ $. Taking the transpose of these equations gives $\ \ u_j ^\intercal Ss_i = 0\ $ for $\ j=1,2,\dots,i-1\ $—that is, $\ Ss_i \in \langle u_1, u_2, \dots, u_{i-1}\rangle^\perp\ $.