IntroductionEigenvalues and EigenvectorsInverse Eigenvalue Problems (IEP's)One Simple AlgorithmHeuvers' AlgorithmProofAn ExampleBenefits and DrawbacksApplicationsIntroduction One Simple Algorithm ApplicationsInverse Eigenvalue ProblemsConstructing Matrices with Prescribed EigenvaluesN. JacksonDepartment of MathematicsCollege of the RedwoodsMath 45 Term Project, Fall 2010Inverse Eigenvalue Problems College of the RedwoodsIntroduction One Simple Algorithm ApplicationsOutlineIntroductionEigenvalues and EigenvectorsInverse Eigenvalue Problems (IEP’s)One Simple AlgorithmHeuvers’ AlgorithmProofAn ExampleBenefits and DrawbacksApplicationsInverse Eigenvalue Problems College of the RedwoodsIntroduction One Simple Algorithm ApplicationsEigenvalues and EigenvectorsWhat are Eigenvalues and Eigenvectors?IAn eigenvalue is “any number such that a given squarematrix minus that number times the identity matrix has azero determinant” [2].IAx = λxInverse Eigenvalue Problems College of the RedwoodsIntroduction One Simple Algorithm ApplicationsEigenvalues and EigenvectorsWhat are Eigenvalues and Eigenvectors?IAn eigenvalue is “any number such that a given squarematrix minus that number times the identity matrix has azero determinant” [2].IAx = λxInverse Eigenvalue Problems College of the RedwoodsIntroduction One Simple Algorithm ApplicationsInverse Eigenvalue Problems (IEP’s)Inverse Eigenvalue Problems (IEP’s)IA well-studied yet continually developing branch of LinearAlgebra concerning construction of matrices from spectraldata.[3]ITwo basic components: solvability and computability.Inverse Eigenvalue Problems College of the RedwoodsIntroduction One Simple Algorithm ApplicationsInverse Eigenvalue Problems (IEP’s)Inverse Eigenvalue Problems (IEP’s)IA well-studied yet continually developing branch of LinearAlgebra concerning construction of matrices from spectraldata.[3]ITwo basic components: solvability and computability.Inverse Eigenvalue Problems College of the RedwoodsIntroduction One Simple Algorithm ApplicationsHeuvers’ AlgorithmKonrad Heuvers’ AlgorithmSymmetric Matrices with Prescribed Eigenvalues and EigenvectorsILet {p1, p2, . . . , pn} be an arbitrary orthonormal basis forRn. These will become the eigenvectors.ILet λ1, λ2, ..., λnbe n arbitrary real numbers (the desiredeigenvalues) and τ be any real number such that τ ≤ λjforj = 1, 2, ..., n.IDefine µj=pλj− τ and bj= µjpj, and let B be the matrixcomprised of the column vectors b1, b2, ...bn.ILet S be the matrix S = BBT+ τI, a symmetric matrix withthe above eigenvectors and eigenvalues.Inverse Eigenvalue Problems College of the RedwoodsIntroduction One Simple Algorithm ApplicationsHeuvers’ AlgorithmKonrad Heuvers’ AlgorithmSymmetric Matrices with Prescribed Eigenvalues and EigenvectorsILet {p1, p2, . . . , pn} be an arbitrary orthonormal basis forRn. These will become the eigenvectors.ILet λ1, λ2, ..., λnbe n arbitrary real numbers (the desiredeigenvalues) and τ be any real number such that τ ≤ λjforj = 1, 2, ..., n.IDefine µj=pλj− τ and bj= µjpj, and let B be the matrixcomprised of the column vectors b1, b2, ...bn.ILet S be the matrix S = BBT+ τI, a symmetric matrix withthe above eigenvectors and eigenvalues.Inverse Eigenvalue Problems College of the RedwoodsIntroduction One Simple Algorithm ApplicationsHeuvers’ AlgorithmKonrad Heuvers’ AlgorithmSymmetric Matrices with Prescribed Eigenvalues and EigenvectorsILet {p1, p2, . . . , pn} be an arbitrary orthonormal basis forRn. These will become the eigenvectors.ILet λ1, λ2, ..., λnbe n arbitrary real numbers (the desiredeigenvalues) and τ be any real number such that τ ≤ λjforj = 1, 2, ..., n.IDefine µj=pλj− τ and bj= µjpj, and let B be the matrixcomprised of the column vectors b1, b2, ...bn.ILet S be the matrix S = BBT+ τI, a symmetric matrix withthe above eigenvectors and eigenvalues.Inverse Eigenvalue Problems College of the RedwoodsIntroduction One Simple Algorithm ApplicationsHeuvers’ AlgorithmKonrad Heuvers’ AlgorithmSymmetric Matrices with Prescribed Eigenvalues and EigenvectorsILet {p1, p2, . . . , pn} be an arbitrary orthonormal basis forRn. These will become the eigenvectors.ILet λ1, λ2, ..., λnbe n arbitrary real numbers (the desiredeigenvalues) and τ be any real number such that τ ≤ λjforj = 1, 2, ..., n.IDefine µj=pλj− τ and bj= µjpj, and let B be the matrixcomprised of the column vectors b1, b2, ...bn.ILet S be the matrix S = BBT+ τI, a symmetric matrix withthe above eigenvectors and eigenvalues.Inverse Eigenvalue Problems College of the RedwoodsIntroduction One Simple Algorithm ApplicationsProofProof of Heuvers’ AlgorithmIThe columns of B are(b1, b2, . . . , bn) = (µ1p1, µ2p2, . . . , µnpn).IThe rows of BTare of the form µipTi.IIt must be shown that Spj= λjpj.Inverse Eigenvalue Problems College of the RedwoodsIntroduction One Simple Algorithm ApplicationsProofProof of Heuvers’ AlgorithmIThe columns of B are(b1, b2, . . . , bn) = (µ1p1, µ2p2, . . . , µnpn).IThe rows of BTare of the form µipTi.IIt must be shown that Spj= λjpj.Inverse Eigenvalue Problems College of the RedwoodsIntroduction One Simple Algorithm ApplicationsProofProof of Heuvers’ AlgorithmIThe columns of B are(b1, b2, . . . , bn) = (µ1p1, µ2p2, . . . , µnpn).IThe rows of BTare of the form µipTi.IIt must be shown that Spj= λjpj.Inverse Eigenvalue Problems College of the RedwoodsIntroduction One Simple Algorithm ApplicationsProofProof (cont., 2)Spj= (BBT+ τI)pj= BBTpj+ τpj= [µ1p1, µ2p2, . . . , µnpn]µ1pT1µ2pT2...µnpTnpj+ τpj= [µ1p1, µ2p2, . . . , µnpn]µ1pT1pjµ2pT2pj...µnpTnpj+ τpjInverse Eigenvalue Problems College of the RedwoodsIntroduction One Simple Algorithm ApplicationsProofProof (cont., 3)IColumn vector all zeros except pjdotted with itself is one.I. . . = [µ1p1, µ2p2, . . . , µnpn]µ1pT1pjµ2pT2pj...µnpTnpj+ τpj= [µ1p1, µ2p2, . . . , µnpn]0...µj...0+ τpjInverse Eigenvalue Problems College of the RedwoodsIntroduction One Simple Algorithm ApplicationsProofProof (cont., 3)IColumn vector all zeros except pjdotted with itself is one.I. . . = [µ1p1, µ2p2, . . . , µnpn]µ1pT1pjµ2pT2pj...µnpTnpj+ τpj= [µ1p1, µ2p2, . . . , µnpn]0...µj...0+ τpjInverse