The Hadamard Product - UPS

1 TheHadamardProductElizabeth MillionApril 12, 20071 Introduction and Basic ResultsAs inexperienced mathematicians we may have once thought that the natural definition for matrixmultiplication would be entrywise multiplication, much in the same way that a young child mightsay, I writed my name. The mistake is understandable, but it still makes us cringe. Unlike poorgrammar, however, entrywise matrix multiplication has reason to be studied; it has nice propertiesin matrix analysis and has applications in both statistics (301 [4], 140 [5]) and physics (93, 149 [5]).Here we will only expore the properties of the Hadamard Product in matrix nmatrices with entries inC. TheHadamard productof Aand B is defined by[A B]ij= [A]ij[B]ijfor all1 i m,1 j we can see, the Hadamard Product is simply entrywise multiplication. Because of this, theHadamard Product inherits the same benefits (and restrictions) of multiplication inC.

2 Note alsothat bothAandBneed to be the same size, but not necessarily square. To avoid confusion,juxtaposition of matrices will imply the usual matrix multiplication, and we will always use for the Hadamard we can explore some basics properties of the Hadamard nmatrices with entries inC. ThenA B=B proof follows directly from the fact that multiplication inCis commutative. LetAandBbem nmatrices with entries inC. Then [A B]ij= [A]ij[B]ij= [B]ij[A]ij= [B A]ijandthereforeA B=B identity matrix under the Hadamard Product is them nmatrix with all entriesequal to 1, denotedJmn. That is,[Jmn]ij= 1for all1 i m,1 j : we have denoted the Hadamard identity asJmnas to avoid confusion with the usual identity matrix, anym nmatrixAwith entries inC. Then [Jmn A]ij= (1)([A]ij) = [A]ijand soJmn A=A. Since the Hadamard Product is commutative ( ), we knowJmn A=A Jmn= ,Jmnas defined above is indeed the identity matrix under the Hadamard anm nmatrix.

3 ThenAhas a Hadamard inverse, denoted A, if andonly if[A]ij6= 0for all1 i m,1 j n. Furthermore,[ A]ij= ([A]ij) ( ) LetAbe anm nmatrix with Hadamard inverse A. Then we knowA A=Jmn. Thatis, [A A]ij= [A]ij[ A]ij= 1. Multiplying by inverses inCwe know that [ A]ij= (1)(([A]ij) 1) =([A]ij) 1, which is only possible when all entries ofAare invertible (inC). In other words, [A]ij6= 0for all 1 i m, 1 j n.( ) Take anym nmatrixAwith entries inCsuch that [A]ij6= 0 for all 1 i m, 1 j there exists ([A]ij) 1for alli,j. This implies [A]ij([A]ij) 1= ([A]ij) 1[A]ij= 1, and soAhasan inverse Adefined by [ A]ij= ([A]ij) 1for alli, : again we have denoted the Hadamard inverse as Aas to avoid confusion with the usual matrix inverse,A Hadamard identity matrix and the Hadamard inverse are both more limiting than helpful,so we will not explore their use further. One last fun fact: the set ofm nmatrices with nonzeroentries form an abelian (commutative) group under the Hadamard Product (Prove this!)

4 Theorem Hadamard Product is C, andA,BandCarem nmatrices. ThenC (A+B) =C A+C B. Furthermore, (A B) = ( A) B=A ( B). 1.[C (A+B)]ij= [C]ij[A+B]ij= [C]ij([A]ij+ [B]ij)= [C]ij[A]ij+ [C]ij[B]ij= [C A]ij+ [C B]ij= [C A+C B]ijPart 2.[ (A B)]ij= [A B]ij= [A]ij[B]ij= [ A]ij[B]ij= [ A B]ijFirst Equality= [A]ij[B]ij= [A]ij [B]ij= [A]ij[ B]ij= [A B]ijSecond Equality2 Diagonal Matrices and the Hadamard ProductWe can relate the Hadamard Product with matrix multiplication via considering diagonal matrices,sinceA B=ABif and only if bothAandBare diagonal. For example, a simple calculationreveals that the Hadamard Product relates the diagonal values of a diagonalizable matrixAwithits eigenvalues:Theorem a diagonalizable matrix of sizenwith eigenvalues 1, 2,.., nanddiagonalizationA=SDS 1whereDis a diagonal matrix such that[D]ii= ifor all1 i , let[A]ij=aijfor alli,j. Then =[S (S 1)T] 1 n (304, [4]).

5 Cnsuch that [d]i= ifor all 1 i n. We will showaii= [S (S 1)Td] [A]ii= [SDS 1]ii=n j=1n k=1[S]ik[D]kj[S 1]ji=n k=1[S]ik[D]kk[S 1]ki=n k=1[S]ik k[S 1]ki=n k=1[S]ik[S 1]ki k=n k=1[S]ik[(S 1)T]ik k=n k=1[S (S 1)T]ik k=n k=1[S (S 1)T]ik[d]k= [S (S 1)Td]iWe obtain a similar result when we look at the singular value decomposition of a square matrices:Theorem a matrix of sizenwith singular values 1, 2,.., nand singular valuedecompositionA=U DV , whereDis a diagonal matrix with[D]ii= ifor all1 i n. Then, =[U V] 1 n Note that this relation only makes sense with square matrices, since otherwise we cannot computeU that (V )T= V. The proof is similar to our proof of ( ).We have started to see that the Hadamard Product behaves nicely with respect to diagonalmatrices and normal matrix multiplication. The following are some more general properties thatexpand on this idea. The proofs all involve straightforward sum manipulation and are left asexercises for the ,Barem nmatrices, andDandEare diagonal matrices of sizemandn, respectively.

6 Then,D(A B)E= (DAE) B= (DA) (BE)= (AE) (DB) =A (DBE)(304, [4])3We will need a quick definition before our next the diagonal matrix,Dx, of sizenwith entries from a vectorx Cnby[Dx]ij={[x]iifi=j, ,Barem nmatrices andx Cn. Then theith diagonal entry of thematrixADxBTcoincides with theith entry of the vector(A B)xfor alli= 1,2, .. , m(305, [4]).That is,[ADxBT]ii= [(A B)x]ifor all1 i ,BandCbem nmatrices. Then theith diagonal entry of the matrix(A B)CTcoincides with theith diagonal entry of the matrix(A C)BT. That is,[(A B)CT]ii=[(A C)BT]iifor all1 i m(305, [4]).3 Schur Product TheoremThe purpose of this section is to set up and prove the Schur Product Theorem. This theoremrelates positive definite matrices to the Hadamard Product , which is important when analyzing thedeterminants of matrices since we want real, nonnegative numbers to compare. Note that ifAispositive semidefinite of sizenthen clearly|A|= ni=1 i 0 since i 0 for all 1 i rank one positive semidefinite matrixAof sizencan be written as the productA=xxTwherexis some vector proof follows the constructive proof of Theorem ROD [3].}

7 LetAbe a rank one positive semidefinite matrix of sizen. SinceAis positive semidefinite, weknow it is Hermitian and therefore normal. This allows us to write the orthonormal diagonalizationA=U DU whereDis the matrix of eigenvalues ofAandUis a unitary matrix made up oforthonormalized eigenvectors ofA(Note thatUhas real entries, soU =UT). Also sinceAispositive semidefinite, we know all the diagonal values ofDare nonnegative the proof of Theorem ROD [3] we now letX ={u1,..,un}be the columns ofUand letY ={u1,..,un}be the rows ofU (which are the rows ofUT) converted to column vectors(which are the columns ofU). Next we defineAk= kukuTkand we see thatA=A1+..+ rank one, so (ordered properly)A=A1+O+..+O=A1= 1u1uT1. We also know 1>0, so we can definex= 1u1. So now we havexxT= ( 1u1)( 1u1)T= 1u1uT1 1= 1 1u1uT1= 1u1uT1= any positive semidefinite matrixAof rank one and sizencan be writtenxxT, wherex a positive semidefinite matrix of sizenand rankr.

8 Then the matricesB1,..,Brfrom the rank one decomposition ofBare all also positive a positive semidefinite matrix of sizenand rankrwith rank one decompositionB=B1+..+Br. Then from the constructive proof of Theorem ROD [3] together with theorthonormal diagonalization ofBwe know thatBk=U DkU whereUis a unitary matrix andDkis the diagonal matrix with [Dk]kk= kand [Dk]ij= 0 for all other entries. SinceBis positive4semidefinite, then we know that all eigenvalues are positive (as ordered for the decomposition).That is, k>0 for all 1 k r. Clearly thenDkis positive semidefinite for all 1 k consider< Bkx,x>for anyx Cn. Then< Bkx,x>=< U DkU x,x>=< DkU x, U x> is true for all 1 k rand soBkis positive semidefinite for a matrix of sizenand rankr. Furthermore, suppose the matricesB1,..,Brfrom the rank one decomposition ofBare all positive semidefinite. ThenBitself is +..+Bras described above and letx Cn.

9 Then< Bx,x>=<(B1+..+Br)x,x>=< B1x+..+Brx,x>=< B1x,x>+..+< Brx,x> positive Product positive semidefinite matricesof sizen. ThenA Bis also positive (141, [2]). LetAandBbe positive semidefinite matrices of sizen. SupposeBis of rank is true if and only ifB=O, and thereforeA B=O, which is clearly positive supposeBis of rank one. Then we can writeB=xxTfor some vectorx Cn( ). Then [A B]ij= [A]ij[B]ij= [A]ij[x]i[xT]j= [DxADx]ij. Now, sinceAis positive semidefinite,then so isDxADx. Take any vectorv Cn. Then< DxADxv,v>=< ADxv,(Dx) v>=< ADxv, Dxv>=< A(Dxv),(Dxv)> supposeBis of rankr, 1< r n. Then we can decomposeBinto a sum of rank onematricesB1,..,Br(Theorem ROD, [3]) where each matrixBiis also positive semidefinite ( ). ThenA B=A (B1+..+Br) =A B1+..+A Br(Theorem ). We know that eachA Biis positive semidefinite for eachi, and soA Bis positive semidefinite (Lemma ).Therefore for any two positive semidefinite matricesAandB,A Bis also positive Some InequalitiesNow for some matrix analysis.

10 In mathematics, the term analysis means there are tons of in-equalities (I have no proof for this). Recall the importance of the Schur Product Theorem is thatif two matricesAandBare positive semidefinite, then so isA B. This allows us to comparedeterminants of these matrices, since they are always nonnegative, real s positive semidefinite matrices of sizen. Then|A B| [A]11 [A]nn|B|.5I am not including a proof of Oppenheim s Inequality because it is somewhat long and requiresa bit of setup. However, it is not hard to follow and so instead I will simply refer you to page 144of Bapat [2].Theorem s positive semidefinite of sizen. Then|A| [A]11 [A] any positive semidefinite matrix of sizen. Note thatInis a postive semidefinitematrix of sizen. Now we have the following:|A|= [In]11 [In]nn|A| |In A|(Oppenheim s Inequality)= [A]11 [A]nnCorollary positive semidefinite matrices of sizen.