Explicit formula for orthonormalized vectors (using Gram-Schmidt)

gram-schmidtlinear algebraorthogonal matrices

For $n\in\mathbb{N}$, let
$$
B(n):=\{b_1,b_2,\ldots,b_n\}:=\left\{\begin{pmatrix}1\\2\\3\\4\\\vdots\\n\end{pmatrix},\begin{pmatrix}2\\-1\\0\\0\\\vdots\\0\end{pmatrix},\begin{pmatrix}3\\0\\-1\\0\\\vdots\\0\end{pmatrix},\begin{pmatrix}4\\0\\0\\-1\\\vdots\\0\end{pmatrix},\ldots,\begin{pmatrix}n\\0\\0\\0\\\vdots\\-1\end{pmatrix}\right\}.
$$
Now I would like to orthogonalize (by Gram-Schmidt) and then normalize $B(n)$.

Question: Is it possible to determine the orthonormalized vectors explicitly?

I write the vectors $b_k\in B(n)~(k=1,2,\ldots,n)$ as
$$
b_k=(b_{k,1},b_{k,2},\ldots,b_{k,k},b_{k,k+1},\ldots,b_{k,n})^T.
$$
where $b_{k,1}=k$ and $b_{k,k}=-1$ while $b_{k,i}=0$ otherwise. Hence, for $k,j\geq 2$ and $k\neq j$, I note that $b_k\cdot b_j= kj$ and $b_k\cdot b_k=k^2+1$.

Moreoever, since $b_k\cdot b_1=0$ for all $k\geq 2$, the orthogonalized vectors, which I denote by $C(n):=\{c_1,c_2,\ldots,c_n\}$, are
$$
\begin{align*}
c_1&:=b_1,\\
c_2&:=b_2,\\
c_k&:=b_k-\frac{2k}{5}b_2-\sum_{i=3}^{k-1}\frac{c_i\cdot b_k}{c_i\cdot c_i}c_i,\quad k\geq 3
\end{align*}
$$

And if we normalize, $d_k:=\frac{c_k}{\sqrt{c_k\cdot c_k}}$ one has the desired set $D(n):=\{d_1,d_2,\ldots,d_n\}$ of orthonormalized vectors.

For the first three vectors, what I get is:
$$
\begin{align*}
d_1&=\frac{b_1}{\sqrt{b_1\cdot b_1}}=\frac{b_1}{\sqrt{\frac{1}{6}(n(n+1)(2n+1))}}=\frac{1}{\sqrt{\frac{n(n+1)(2n+1)}{6}}}\begin{pmatrix}1\\2\\3\\\vdots\\n\end{pmatrix}\\
d_2&=\frac{b_2}{\sqrt{b_2\cdot b_2}}=\frac{b_2}{\sqrt{5}}=\begin{pmatrix}\frac{2}{\sqrt{5}}\\-\frac{1}{\sqrt{5}}\\0\\\vdots\\0\end{pmatrix}\\
d_3&=\frac{5}{\sqrt{70}}c_3,\quad c_3=b_3-\frac{6}{5}b_2=\begin{pmatrix}\frac{3}{5}\\\frac{6}{5}\\-1\\0\\\vdots\\0\end{pmatrix}\\
d_4&=\frac{c_4}{\sqrt{c_4\cdot c_4}},\quad c_4=b_4-\frac{8}{5}b_2-\frac{c_3\cdot b_4}{c_3\cdot c_3}c_3=?
\end{align*}
$$

But I don't see a way to reach explicit formulae for $d_j~(j=1,2,3,\ldots,n)$ in general.

Best Answer

It seems that $$v_k=(1,2,3,\ldots,k-1,-x_k,0,\ldots,0)$$ works for constants $x_k$ that are easy to work out by dotting with $b_1$. Then normalize each $v_k$. If $v_k$ is normal to $v_1$ then it is normal to $v_h$ for all $h\gt k$

Related Solutions

[Math] Compute the change of basis matrix in Matlab

Basically, your explanation is hard to follow because of a mixture between column and row vectors.

You should stick to a certain convention: every time you consider a vector known through its components with respect to a a basi, connect it with a column vector (this is the most usual convention), with notation $V$, and stick to notation $V^T$ if it is a row vector.

If such a convention is used, if we consider $B = (b_1, ... , b_n)$ and $D = (d_1, ... , d_n)$ (where the $b_k$ and the $d_k$ are column vectors), then, $B$ and $D$ are $n \times n$ matrices. We have the equivalence:

$$(\forall k, Sb_k=d_k) \ \Rightarrow \ SB=D \ \ (1)$$

From formula (1), the matrix you are looking for (as you say more or less) is simply

$$S=DB^{-1} \ \ (2)$$

For example, if you want the matrix $S$ sending $b_1=$$1 \choose 1$ and $b_2=$$-1 \choose 1$ to $d_1=$$0 \choose 1$ and $d_2=$$ -1 \choose 0$ resp., formula (2) gives:

$$S=\begin{pmatrix} 0 & -1\\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & -1\\ 1 & 1 \end{pmatrix}^{-1}=\frac{1}{2}\begin{pmatrix} 1 & -1\\ 1 & 1 \end{pmatrix}$$

Are matrices which yield a given characteristic polynomial and have specified structure connected

$\newcommand{\NN}{{\mathbb{N}}}\newcommand{\CC}{{\mathbb{C}}}\newcommand{\RR}{{\mathbb{R}}}\newcommand{\ra}{\rightarrow}\newcommand{\ds}{\displaystyle}$

The answer might be surprising: If the characteristic polynomial $p(t)$ has at least one real zero then the set $f^{-1}(p)$ is connected. If $p(t)$ has no real zeros than it consists of three connected components.

The starting point of my solution is the observation that the characteristic polynomial $p(t)= t^4 + a_3 t^3 + a_2 t^2 + a_1 t + a_0$ of $A$ in $f^{-1}(p)$, \begin{align*} A = \begin{pmatrix} 0 & -b_1 & 0 & -c_1 \\ 1 & -b_2 & 0 & -c_2 \\ 0 & -b_3 & 0 & -c_3 \\ 0 & -b_4 & 1 & -c_4 \\ \end{pmatrix}, \end{align*} is calculated as \begin{equation}\tag{1}\label{eq1} p(t)= (t^2+b_2t+b_1)(t^2+c_4t+c_3)-(b_4t+b_3)(c_2t+c_1). \end{equation} It is tempting to vary $b_4,b_3,c_2,c_1$ as parameters and determine $b_2,b_1,c_4,c_3$ from a real factorisation of the polynomial $p(t)+(b_4t+b_3)(c_2t+c_1)$. While such a factorisation always exists (not unique in general), it does not depend continuously upon the parameters, that is if we vary $b_4,b_3,c_2,c_1$ continuously on some path in $\mathbb R^4$, then it might be impossible to choose corresponding factorisations in a continuous way. This can be seen using the complex roots of $(t^2+b_2t+b_1)(t^2+c_4t+c_3)$, but it is not the question here.

Instead, I will use $b_1,b_2,b_3,b_4$ as parameters and determine $c_1,c_2,c_3,c_4$ by solving the linear equation (\ref{eq1}). This leads to a system of linear equations \begin{equation}\tag{2}\label{eq2} \begin{array}{rcrcrcrcl} &&&&&&c_4&=&a_3-b_2\\ &-&b_4\,c_2&+&c_3&-&b_2\,c_4&=&a_2-b_1\\ -b_4c_1&-&b_3\,c_2&+&b_2\,c_3&+&b_1\,c_4&=&a_1\\ -b_3\,c_1&&&+&b_1\,c_3&&&=&a_0. \end{array} \end{equation} Its determinant is $d(b_1,b_2,b_3,b_4)=b_3^2-b_2b_3b_4+b_1b_4^2$. If $b_4\neq0$ then it vanishes if and only if the two polynomials $t^2+b_2t+b_1$ and $b_4t+b_3$ have a common zero, namely $t=-b_3/b_4$. Whenever $d(b_1,b_2,b_3,b_4)\neq0$, the parameters $b_j$ determine $c_1,c_2,c_3,c_4$ uniquely. If the parameters vary continuously along some path in $\RR^4$ on which $d$ does not vanish, then so do the corresponding $c_j$.

Given a matrix $A$ in $f^{-1}(p)$, we will now try to reduce it within $f^{-1}(p)$ to the block diagonal form indicated by MyCindy2012. During the proof, it will also become clear that all such block diagonal matrices can be connected by paths within $f^{-1}(p)$. We have to consider several cases. The trivial ones that $b_3=b_4=0$ or $c_1=c_2=0$ are excluded in the sequel because $c_1,c_2$ or $b_3,b_4$, respectively, can be reduced to zero without changing anything else.

If $b_4=0$ and $b_3\neq0$, then $d(b_1,b_2,b_3,b_4)\neq0$ whatever $b_1,b_2$ and hence they can be chosen arbitrarily and, by (\ref{eq2}), $c_1,c_2,c_3,c_4$ are uniquely determined. Therefore we can reduce $b_1,b_2$ to those values correponding to some real factorisation $p(t)= (t^2+b_2t+b_1)(t^2+c_4t+c_3)$ of $p$. By the uniqueness, we must then have $c_1=c_2=0$ and we reach the block diagonal form. Observe that in this case, we can reach {\em any} real factorisation of $p(t)$. Trivially the present case can be reached from any real factorisation of $p(t)$ ad therefore they can all be connected by paths within $f^{-1}(p)$. In the sequel we assume that $b_4\neq0$ tacitly.
If $d(b_1,b_2,b_3,b_4)=b_3^2-b_2b_3b_4+b_1b_4^2 >0$ then we can first increase $b_1$ to a sufficiently large value, then reduce $b_2$ to $0$ and finally reduce $b_4$ to 0 without leaving the set $b_3^2-b_2b_3b_4+b_1b_4^2 >0$. Completing these $b_j$ by $c_k$ from system (\ref{eq2}), we obtain a path in the subset of $f^{-1}(p)$ on which $b_3^2-b_2b_3b_4+b_1b_4^2 >0$. As it leads to case 1, we are done.
If $d(b_1,b_2,b_3,b_4)=0$, then $t^2+b_2t+b_1$ and $b_4t+b_3$ have common zero $z=-b_3/b_4$ and thus a common factor $t-z$. By (\ref{eq1}), $t-z$ must also be a factor of $p(t)$ and we can divide (\ref{eq1}) by $t-z$ to obtain \begin{equation}\tag{3}\label{eq3} q(t)=t^3+d_2t^2+d_1t+d_0=(t+h)(t^2+c_4t+c_3)-g_1t-g_2 \end{equation} with $d_0,d_1,d_2,g_1,g_2,h$ related to previous coefficients. We write $q=F(c_3,c_4,g_1,g_2,h)$.
We now show that for any given $q$, the set $F^{-1}(q)$ is connected. It is convenient to assume that $d_2=0$. This is not a loss of generality as replacing $t$ by $t-\frac13d_2$ in (\ref{eq3}) leads to an equivalent situation. If we denote the zeroes of $t^2+c_4t+c_3$ by $z_1,z_2$ (Attention, . they might be conjugate complex) then for $s$, $0\leq s\leq 1$, the product $t^2+sc_4t+s^2c_3=(t-sz_1)(t-sz_2)$ and the product $(t+sh)(t^2+sc_4t+s^2c_3)$ has the zeroes $sh,sz_1,sz_2$. Putting $$g_1(s)t+g_2(s)=(t+sh)(t^2+sc_4t+s^2c_3)-q(t),$$ we obtain for each $s$ a decomposition (\ref{eq3}) in $F^{-1}(q)$. Therefore any decomposition (\ref{eq3}), $d_2=0$, can be reduced within $F^{-1}(q)$ to $q(t)=t\cdot t^2+d_1t+d_0$ by letting $s$ vary from 1 to 0. As a consequence, any two decompositions (\ref{eq3}) are connected within $F^{-1}(q)$.
For our purpose, we reduce $g_1,g_2$ to 0. In the corresponding problem for our polynomial of degree 4, this means that we can reach $c_1=c_2=0$ and we are done.
If $d(b_1,b_2,b_3,b_4)=b_3^2-b_2b_3b_4+b_1b_4^2 <0$ and $p$ has at least one real zero, say $t=z$, then we first reduce $b_1$ to a sufficiently large negative value, $b_2$ to 0 and then reduce $b_3$ to the value $b_3=-z\,b_4$. If $b_1$ is sufficiently negative, we remain in the set $b_3^2-b_2b_3b_4+b_1b_4^2 <0$ and can therefore complete with certain $c_j$ to elements of $f^{-1}(p)$. Now $p(t)$ and $b_4t+b_3$ have a common zero: $t=z$. By (\ref{eq1}), it must also be a zero of $t^2+c_4t+c_3$, since it is not a zero of $t^2+b_2t+b_1$. Therefore $t^2+c_4t+c_3$, $b_4t+b_3$ and $p(t)$ can be divided by $t-z$ and we obtain a problem for a polynomial of degree 3 analogous to the one in case 3. Again, we can reach the block diagonal form.
If $d(b_1,b_2,b_3,b_4)=b_3^2-b_2b_3b_4+b_1b_4^2 <0$ and $p$ has no real zeroes then we cannot reach a block diagonal form. In fact, we cannot reach any point in $f^{-1}(p)$ where $d$ vanishes (and hence also no point where $d$ is positive). To show this, assume that we have decompositions \begin{equation} p(t)= (t^2+b_2(s)t+b_1(s))(t^2+c_4(s)t+c_3(s))-(b_4(s)t+b_3(s))(c_2(s)t+c_1(s)). \end{equation} with coefficients depending continuously upon $s$, $0\leq s\leq 1$, that $b_3(s)^2-b_2(s)b_3(s)b_4(s)+b_1(s)b_4(s)^2<0$ for $s<1$ whereas $b_3(1)^2-b_2(1)b_3(1)b_4(1)+b_1(1)b_4(1)^2=0$. We cannot have $b_4(1)\neq0$ because then, as shown in case 3, $p(t)$ has a linear term $t-z$ as a factor contradicting the assumption that it does not have real zeroes. Therefore $b_4(1)=b_3(1)=0$ and for $s=1,$ we have reached a real factorisation of $p(t)$. Hence the two quadratic factors have no real roots and therefore negative discriminant, in particular $b_2(1)^2-4b_1(1)<0$.
On the other hand, for $s<1$ we must have $b_4(s)\neq0$ and the polynomial $t^2+b_2(s)t+b_1(s)$ has a negative value at $t=-b_3(s)/b_4(s)$. Therefore, it has positive discriminant: $b_2(s)^2-4b_1(s)>0$ for $s<1.$ By continuity, we must have $b_2(1)^2-4b_1(1)\geq0$ and have reached a contradiction.
Observe that is this case, we must also have $c_1^2-b_2c_1c_2+b_1c_2^2<0$, because in (\ref{eq1}), $c_2t+c_1$ might replace the other linear term $b_4t+b_3$. If $c_1^2-b_2c_1c_2+b_1c_2^2\geq0$ then we can reach a block diagonal decomposition in $f^{-1}(c)$ -- as shown in case 2 and 3 -- but this is not possible. Similarly, we have $b_3^2-c_4b_3b_4+c_3b_4^2<0$, $c_1^2-c_4c_1c_2+c_3c_2^2<0$.
We also show that the subset of $f^{-1}(p)$ on which $b_3^2-b_2b_3b_4+b_1b_4^2 <0$ has two connected components. Clearly, it must have at least two components, because $b_4$ cannot vanish on it. On the other hand from any starting point, we can first decrease $b_1$ to sufficiently large negative $b_1$ and then reduce $b_2$ and $b_3$ to 0 and $b_4$ to $1$ or $-1$. The corresponding $c_j$ are again uniquely determined from system (\ref{eq2}). Therefore the subset of $f^{-1}(p)$ on which $b_3^2-b_2b_3b_4+b_1b_4^2 <0$ has exactly two connected components in the present case and together with case 2, $f^{-1}(p)$ has exactly 3 connected components in the case that $p$ has no real zeroes.

Edit: 1. Observe that it is not necessary in this proof that $p(t)$ is squarefree.
2. In the complex domain. $f^{-1}(p)$ is always connected. $p(t)$ has always zeros, factorisations into quadratic factors can be continued as cntinuous functions and elimination of finitely many points of $\mathbb C$ still leaves a connected set.
3. For completeness, here is an example of a continuous family of monic real polynomials of degree 4 for which there does not exist a continuous real factorisation into quadratic factors. We define the polynomials by giving their zeros.
First for $s$ from $1$ downto $0$, the zeros are $\pm1\pm s\,i$, then for $a$ from $1$ downto $0$, they are $\pm1$ and $\pm s$, finally for $b$ from $0$ to $1$ they are $\pm1$ and $\pm bi$.
The factorisation must then be (except for ordering) $(t^2+2t+1+s^2)(t^2-2t+1+s^2)$ for $s$ from $1$ downto 0, then $(t^2+(1+a)t+a)(t^2-(1+a)t+a)$ for $a$ from 1 downto 0 and it jumps to $(t^2-1)(t^2+b^2)$ at this point.

Best Answer

Related Solutions

[Math] Compute the change of basis matrix in Matlab

Are matrices which yield a given characteristic polynomial and have specified structure connected

Related Question