{"id":8338,"date":"2015-04-05T18:48:49","date_gmt":"2015-04-05T16:48:49","guid":{"rendered":"http:\/\/djalil.chafai.net\/blog\/?p=8338"},"modified":"2015-06-17T17:38:51","modified_gmt":"2015-06-17T15:38:51","slug":"an-exercise-in-linear-algebra","status":"publish","type":"post","link":"https:\/\/djalil.chafai.net\/blog\/2015\/04\/05\/an-exercise-in-linear-algebra\/","title":{"rendered":"An exercise in linear algebra"},"content":{"rendered":"

\"Matrix\"<\/a><\/p>\n

Exercise.<\/b> Recently a friend of mine asked the following basic question: suppose that \\( {H} \\) is a \\( {n\\times n} \\) Hermitian matrix with \\( {>0} \\) spectrum and suppose that \\( {P} \\) is a \\( {n\\times n} \\) orthogonal projection matrix. Is it true that all the non-zero eigenvalues of the product \\( {HP} \\) are above the least eigenvalue of \\( {H} \\)?<\/p>\n

Quick proof (suggested by a colleague).<\/b> Since \\( {P} \\) is an orthogonal projection, we have<\/p>\n

\\[ P^*=P=P^2. \\]<\/p>\n

Let \\( {x} \\) be an eigenvector of \\( {HP} \\) associated with a non zero eigenvalue \\( {\\lambda} \\), meaning that \\( {HPx=\\lambda x\\neq0} \\). Note that \\( {Px\\neq0} \\) otherwise \\( {HPx=0} \\). Now if \\( {\\lambda_*} \\) is the smallest non-zero eigenvalue of \\( {H} \\) then \\( {\\lambda_*>0} \\) and<\/p>\n

\\[ \\left\\Vert Px\\right\\Vert_2^2\\lambda_* \\leq\\left<Px,HPx\\right> =\\left<Px,\\lambda x\\right> =\\lambda\\left<Px,Px\\right> =\\lambda\\left\\Vert Px\\right\\Vert_2, \\]<\/p>\n

which shows that \\( {\\lambda} \\) is real and \\( {\\lambda_*\\leq\\lambda} \\) as expected.<\/p>\n

Comments.<\/b> There exists a unitary matrix \\( {U} \\) such that \\( {UPU^*} \\) is diagonal with diagonal in \\( {\\{0,1\\}} \\). If \\( {H} \\) and \\( {P} \\) commute, then \\( {UHU^*} \\) is also diagonal, with diagonal elements in \\( {\\mathbb{R}_+} \\), and therefore \\( {UHPU^*} \\) is diagonal with diagonal elements in \\( {\\{0\\}\\cup\\mathrm{spectrum}(H)} \\). This shows that the problem has positive answer when \\( {H} \\) and \\( {P} \\) commute.<\/p>\n

In the general situation, \\( {H} \\) and \\( {P} \\) do not commute, and the product \\( {HP} \\) is not necessarily Hermitian even if \\( {H} \\) and \\( {P} \\) are Hermitian. We may use the fact that \\( {AB} \\) and \\( {BA} \\) have same spectrum. This is a consequence of the Sylvester determinant theorem<\/a> which states that<\/p>\n

\\[ \\det(I+AB)=\\det(I+BA). \\]<\/p>\n

As a consequence, if \\( {A} \\) and \\( {B} \\) are both Hermitian with \\( {\\geq0} \\) spectrum, then \\( {AB} \\) has the spectrum of the Hermitian matrix \\( {B^{1\/2}A^{1\/2}A^{1\/2}B^{1\/2}} \\). Therefore, this spectrum is real and \\( {\\geq0} \\), formed by the squared singular values of \\( {A^{1\/2}B^{1\/2}} \\). In particular, if \\( {A=H} \\) is Hermitian with \\( {\\geq0} \\) spectrum and if \\( {B=P} \\) is the matrix of an orthogonal projection, then \\( {AB=HP} \\) has a real \\( {\\geq0} \\) spectrum, formed by the squared singular values of \\( {H^{1\/2}P^{1\/2}=H^{1\/2}P} \\) since \\( {P^{1\/2}=P} \\) (\\( {P} \\) is an orthogonal projection).<\/p>\n

Additional comments.<\/b> If one denotes by \\( {s_1(M)\\geq\\cdots\\geq s_n(M)\\geq0} \\) the singular values of a \\( {n\\times n} \\) matrix \\( {M} \\), then the Courant-Fischer min-max variational formulas<\/a> give, for any \\( {1\\leq k\\leq n} \\),<\/p>\n

\\[ s_k(M) =\\max_{V\\in\\mathcal{V}_k}\\min_{\\substack{v\\in V\\\\\\left\\Vert v\\right\\Vert_2=1}}\\left\\Vert Mv\\right\\Vert_2 \\left(=\\min_{V\\in\\mathcal{V}_{n-k+1}}\\max_{\\substack{v\\in V\\\\\\left\\Vert v\\right\\Vert_2=1}}\\left\\Vert Mv\\right\\Vert_2\\right) \\]<\/p>\n

where \\( {\\mathcal{V}_k} \\) is the set of sub-spaces with dimension \\( {k} \\). Used with \\( {M=H^{1\/2}P} \\),<\/p>\n

\\[ s_k(H^{1\/2}P)=\\max_{V\\in\\mathcal{V}_k}\\min_{\\substack{v\\in V\\\\\\left\\Vert v\\right\\Vert_2=1}} \\left\\Vert H^{1\/2}Pv\\right\\Vert_2. \\]<\/p>\n

If \\( {V\\cap\\mathrm{ker}(P)\\neq\\{0\\}} \\) then there exists \\( {v\\in V} \\) with \\( {\\left\\Vert v\\right\\Vert_2=1} \\) and \\( {\\left\\Vert H^{1\/2}Pv\\right\\Vert_2=0} \\), hence<\/p>\n

\\[ s_k(H^{1\/2}P) =\\max_{\\substack{V\\in\\mathcal{V}_k\\\\V\\cap\\mathrm{ker}(P)\\neq\\{0\\}}} \\min_{\\substack{v\\in V\\\\\\left\\Vert v\\right\\Vert_2=1}} \\left\\Vert H^{1\/2}Pv\\right\\Vert_2. \\]<\/p>\n

Now if \\( {k>d} \\) where \\( {d=n-\\mathrm{dim}(\\mathrm{ker}(P))=\\mathrm{dim}(\\mathrm{Im}(P))} \\), then for every \\( {V\\in\\mathcal{V}_k} \\), we have \\( {V\\cap\\mathrm{ker}(P)\\neq\\{0\\}} \\), and thus \\( {s_k(H^{1\/2}P)=0} \\).<\/p>\n

Let us suppose in contrast now that \\( {k\\leq d} \\). Then there exists \\( {V_*\\in\\mathcal{V}_k} \\) such that \\( {V_*\\subset\\mathrm{Im}(P)\\perp\\mathrm{ker}(P)} \\), and thus, for every \\( {v\\in V_*} \\) such that \\( {\\left\\Vert v\\right\\Vert_2=1} \\), we have \\( {Pv=v} \\), which gives then<\/p>\n

\\[ s_k(H^{1\/2}P) \\geq \\min_{\\substack{v\\in V_*\\\\\\left\\Vert v\\right\\Vert_2=1}} \\left\\Vert H^{1\/2}v\\right\\Vert_2 \\geq \\min_{\\left\\Vert v\\right\\Vert_2=1}\\left\\Vert H^{1\/2}v\\right\\Vert_2 = s_n(H^{1\/2})=s_n(H)^{1\/2}. \\]<\/p>\n

As a conclusion we have, still with \\( {d=\\mathrm{dim}(\\mathrm{Im}(P))} \\),<\/p>\n

\\[ s_1(HP)\\geq\\cdots\\geq s_d(HP)\\geq s_n(H) \\]<\/p>\n

\\[ s_{d+1}(HP)=\\cdots=s_n(HP)=0. \\]<\/p>\n

Alternative.<\/b> Actually, the result can be deduced quickly from the following general bound, which is also a consequence of Courant-Fischer formulas: if \\( {A} \\) and \\( {D} \\) are \\( {n\\times n} \\) with \\( {D} \\) diagonal then for any \\( {1\\leq k\\leq n} \\),<\/p>\n

\\[ s_n(D)s_k(A)\\leq s_k(DA)\\leq s_1(D)s_k(A). \\]<\/p>\n

Indeed, if \\( {P} \\) is an orthogonal projector and if \\( {H=UDU^*} \\) is Hermitian with \\( {\\geq0} \\) spectrum, then the lower bound in the inequality above used with \\( {A=U^*P} \\) gives<\/p>\n

\\[ s_n(H)s_k(P)=s_n(D)s_k(U^*P)\\leq s_k(DU^*P)=s_k(UDU^*P)=s_k(HP). \\]<\/p>\n

Now \\( {s_k(P)=1} \\) if \\( {k\\geq d} \\), where \\( {d=n-\\mathrm{dim}(\\mathrm{ker}(P))=\\mathrm{dim}(\\mathrm{Im}(P))} \\), which gives \\( {s_k(HP)\\geq s_n(H)} \\) if \\( {k\\geq d} \\). On the other hand, using the upper bound we get<\/p>\n

\\[ s_k(HP)=s_k(UDU^*P)=s_k(DU^*P)\\leq s_1(D)s_k(U^*P)=s_1(H)s_k(P). \\]<\/p>\n

Now if \\( {k<d} \\) then \\( {s_k(P)=0} \\), which gives \\( {s_k(HP)=0} \\).<\/p>\n

Further reading.<\/b> Many other bounds are available, see for instance the books<\/p>\n