### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Professionalism, Diversity, and Academic Success in Management M 100

NCS

GPA 3.93

### View Full Document

## 12

## 0

## Popular in Course

## Popular in Business, management

This 152 page Class Notes was uploaded by Alayna Dare on Thursday October 15, 2015. The Class Notes belongs to M 100 at North Carolina State University taught by Staff in Fall. Since its upload, it has received 12 views. For similar materials see /class/224009/m-100-north-carolina-state-university in Business, management at North Carolina State University.

## Reviews for Professionalism, Diversity, and Academic Success in Management

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/15/15

Chapter 4 Structured Inverse Eigenvalue Problems o Jacobi Inverse Eigenvalue Problems 0 Toeplitz Inverse Eigenvalue Problem 0 Nonnegative Inverse Eigenvalue Problem 0 Stochastic Inverse Eigenvalue Problem 0 Unitary Inverse Eigenvalue Problem 0 Inverse Eigenvalue Problem with Prescribed Entries 0 Inverse Singular Value Problems 0 Inverse Singular Eigenvalue Problem 97 98 Structured Inverse Eigenvalue Problems Jacobi Inverse Eigenvalue Problems 0 Overview 0 Subvariations 0 Existence Theory 0 Sensitivity Issues 0 Numerical Methods Jacobi Inverse Eigenvalue Problems 99 Overview 0 Jacobi structure ie a1 b1 0 O 1 a2 b2 0 J I b2 a3 39 0 I gt 0 an l bn l 0 bn l an appears in many areas of applications ltgt Oscillatory mass spring systems ltgt Composite pendulum ltgt Sturm Liouville problems 0 Jacobi IEP often can be solved by direct methods in nitely many steps 0 For symmetric tridiagonal matrices there are 271 1 unknown entries to be determined Thus there is in need of 271 1 pieces of information o For convenience denote the leading principal submatrix of M by M 100 Structured Inverse Eigenvalue Problems Subvariations SIEP6a 4L 95 15a 1641 175 1 197 ltgt Given D Real scalars A z and 1 u1 D Interlacng property Ajgungj Z1n 1 ltgt Find a Jacobi matrix J such that aw Az1 0U Hi7 71324 SIEP2 140 98 193 ltgt Given D Real scalars AZZ1 ltgt Find a persyrnrnetric Jacobi matrix J such that 0U AZZ1 Gr an1 z39 bi bn2 z39 Jacobi Inverse Eigenvalue Problems 101 SIEP6b 259 ltgt Given D Complex and distinct scalars A1 Agn and Mia 76714 6 C D Closed with complex conjugation ltgt Find tridiagonal symmetric matrices C and K for the matrix Q A2 AC K so that 39 7911 lulv 39 39 39 align 2quot D Arising from damped oscillatory systems D Open Question A practical solution requires ad ditional conditions ie positive diagonal entries negative off diagonal entries and are weakly di agonally dominant 102 Structured Inverse Eigenvalue Problems 0 SlEP 40 41 1 29 ltgt Given D Real scalars AZZ1 and 1 u1 D Satisfy the interlacing property D A positive number ltgt Find a periodic Jacobi matrix J of the form a1 1 bn b1 a2 b2 0 0 b2 a3 0 J 3 I an l bn l I Lb bn l an J such that aw Az1 39 39 39 7HZ 17 21 S Jacobi Inverse Eigenvalue Problems 103 SIEP8 seas ltgt Given D Real scalars AZZ1 and 1 njfb D Satisfy the interlacing property Ai i SVlia i17 7717 With fb1oo ltgt Find Jacobi matrices J and J so that 0U AZZ17 at at uzi J J y 0 only at the 7171 position SIEPQ ltgt Given D Distinct real scalars A1 3 D A Jacobi matrix Jn 6 RM ltgt Find a Jacobi matrix Jgn E RQWQ so that 0J2n A Agn J2n1 711 n J 104 Structured Inverse Eigenvalue Problems Physical Interpretations Figure 1 Mass spring system 0 Consider a serially linked mass spring system with 71 particles ltgt ml mass of the i th particle ltgt lei spring constant of the i th spring ltgt 21405 displacement of the i th particle at time t 0 Equation of motion Fit 701 1 l iu1 2u2 U1 2 d UZ39 139 454 ui 1 ki1ltWi Ur 2 2 n i d2 n mn u knun Uri 1 Jacobi Inverse Eigenvalue Problems 105 o In matrix form M K dt u ltgtu u1 uan ltgt M diagm1 mn ltgt K is the Jacobi matrix given by k1 2 lt22 0 0 0 62 k2 3 lt23 0 K I 0 k3 l 3l 4 0 l a quot t l 0 kn 4 o Fundamental solutions are of the form ut emx ltgt Natural frequencymode equation is governed by KX w2MX 0 De ne J l112Kl11 and w2 Then JX X 0 Knowing ml and 1 we can predict the natural fre quencies and modes of the system ltgt The inverse problem means that we would like to kr kr 1 k 1 calculate values such as 2 and H from 77 xmz39mz39Jrl the spectral data 106 Structured Inverse Eigenvalue Problems SIEP6a ltgt Identifying the system from its spectrum and the spectrum of the reduced system Where the last mass is held to have no motion SIEP2 ltgt Identifying the system from its spectrum if the system is symmetric With respect to its center SIEP6b ltgt Identifying the damped system including its damper con gurations from its spectrum and the spectrum of the reduced system Where the last mass is held immboileS SIEP7 ltgt Same as SIEP6a except that m1 and m2 are connected by another spring mechanism to form a loop SIEP8 ltgt Identifying the system from its spectrum and the spectrum of the new system Whereas only the last spring constant is changed SIEP9 ltgt Identifying the system from its spectrum and physical paramters mi kl of the rst half particles Sometimes it is impossible to gather the entire spectrum information Partial information of some eigenvalues and some eigenvectors can also be used to determine a Jacobi matrix See Chapter 6 Jacobi Inverse Eigenvalue Problems 107 Exknencerfheory 0 Very rich and nearly complete theory available 0 Strictly interlacing property ie AfltujltAgh i1wun L is a necessary condition unless some subdiagonal su perdiagona entries are zero ltgt Jacobi matrices are assumed to have positive bl for alli1 n l ltgt Eigenvalues of a Jacobi matrix are necessarily real and distinct ltgt Eigenvalues of J necessarily separate those of J 0 Most existence proofs are based on the recurrence rela tionship between characteristic polynomials for Jacobi matrices 108 Structured Inverse Eigenvalue Problems 0 Assume that the given eigenvalues satisfy the strictly interlacing property Then ltgt The SlEP6a has a unique solution 175 ltgt The SIEP8 has a unique solution 0 If AZZ1 are distinct Then the SIEP2 has a unique solution 0 Over the complex eld C ltgt If the given eigenvalues are distinct then the SlEP6b is solvable and has at most 2 2n 3 n 2 different solutions l28 ltgt If some eigenvalues are common then there are in nitely many solutions for the SlEP6b Jacobi Inverse Eigenvalue Problems 109 0 Assume that 13 24 are distinct Then the SIEP7 is solvable if and only if M A221 2 251 1 j17 k1 for allj1n 1360j ltgt N0 uniqueness can be assumed ltgt The eigenvalues of a periodic Jacobi matrix are not necessarily distinct ltgt The eigenvalues of j need not separate those of a periodic Jacobi matrix J 0 Assume that A1 3 are distinct ltgt De ne 1 1 1 1 Akdet 391 elTJ39nel A511 A l Air 1 elijfblel A3511 A324 ltgt Then the SIEP9 has a unique solution if and only if Ak gt 0 for all k 1 7271 360 110 Structured Inverse Eigenvalue Problems Sensitivity Issues o The function F R2 1 gt R2 1 Where Fa1 an 1 bn1 0U 03 is differentiable if bl gt 0 o The solution J to the SlEP6a depends continuously on the given data AZZ1 and uf7 ujfhl 195 0 Let J and j be solutions to the SIEP6a with data Xfltu flt ltltuj1ltj lt qlt ltlt L 1lt Then there exists a constant K such that 71 71 1 12 HJ JHF K 2 W W Z iii12 11 1 ltgt K depends on the separation of the given data mea sured by d maXA77 m1 jklA MZL W il 60 d minauw ZlalH Hilal Zlvl 2lv 60 2d Jacobi Inverse Eigenvalue Problems 111 Numerical Methods o Lanczos method ltgt Given any matrix A if QTAQ H Where Q is orthogonal and H is upper Hessenberg with positive subdiagonal entries then Q and H are completely determined by A and the rst column of Q ltgt In our application J QTAQ in symmetric diago nal 1 a1 qlTAql 2b12 HAq1 a1q1H 3 C12 Aqi GHQbi 4Fori2 n 1 31 az 3 qZTAqi39 b bi 3 HAW arch brinr ill C Qi1 3 Nb 0er bi lqi 1bz39 5 an quqn o Orthogonal reduction method ltgt Orthogonal tridiagonalization of a bordered diago nal matrix 112 Structured Inverse Eigenvalue Problems Lanczos Method for SlEP6a 0 Basic facts ltgt Given any symmetric matrix A with orthonormal eigenpairs Ai xi then adjZI A Hui Apxixf k1 be ltgt Evaluate the above equation at the 11 position for each X1 to obtain n 1 k1z39 Mk Z HZQW M be c For SlEP6a ltgt The rst column of Q for J can be expressed from the spectral data ie Qil CUM ltgt The Lanczos algorithm kicks in ltgt Need reorthogonalization along the way Jacobi Inverse Eigenvalue Problems 113 Orthogonal Reduction Method for SlEP6a 0 Construct a bordered diagonal matrix A of the form or 51 n1 A 5i Hi 0 n 1 0 HZ IJ With speci ed eigenvalues 0A AZZ1 ltgt 04 is trivially determined 71 11 1 a Z A Z 2 11 11 ltgt Characteristic polynomial of A is known n l detI A A or Ho mg k1 71 71 1 63 HM HZ k rag 39 ML 1 139 NH 114 Structured Inverse Eigenvalue Problems ltgt Border elements z can be calculated 62 Hk1M Ak Z I L l k1ltz Mk be c Derive orthogonal matrix Q ef ciently so that T T T 10TA10 ozblellt 0 Q 0 Q blel J ltgt 51 H H ltgt QTdiasULi wit 062 J ltgt The rst column of Q is given by b b1 ltgt The Lanczos method can be employed 0 One may also explore the bordered diagonal structure by using Householder transformation Givens rotations the Rutishauser method7 and so on Toeplitz Inverse Eigenvalue Problems 115 Toeplitz Inverse Eigenvalue Problem 0 Overview 0 Existence Theory 0 Numerical Methods 116 Structured Inverse Eigenvalue Problems Overview o Symmetric Toeplitz Matrix TO tij rjl1 ie T1 T2 Tn1 Tn 7 2 7 1 731 2 731 1 7414 7 1 7 2 J Tn 734 73 7 1 0 Is a special case of centrosymmetric matrices Cn MlM MT M EME ltgt E unit perdiagonal matrix 5m Sm 31 D Symmetric vector if Eu u D Skew symmetric vector if Eu u o TOIEP Find 7 E R such that TO has a prescribed set of real numbers AZZ1 as its spectrum Toeplitz Inverse Eigenvalue Problems 117 Spectral Properties of Centrosymmetrie Matrices c Any M E C can be decomposed as follows 55 n even odd A170T Al 14 Cq mT mT CEAE q ClErEAE I I 0 E K 1 0 0 H O E KMKT 0 q mT A EC 0 J 0 AEC A EC O O O AEC ltgtACE e RLMJ ltgtI E RLgJ ltgtq E R 0AAT 118 Structured Inverse Eigenvalue Problems 0 Orthonorrnal eigenvectors Q KTZ M can be split into two groups based on diagonal block Z i Z1 0 z 7 O Z2 ltgt Z1 Eigenvectors of A EC T ltgt Z2 Eigenvectors of q x or AEC x A EC 0 Eigenvectors of M enjoy special parity properties Z ltgtKT 1 skew symmetric eigenvectors gt Odd eigenvalues 0 ltgt KT Z J syrnrnetric eigenvectors gt Even 2 eigenvalues 0 Open Question For an TOIEP to be solvable each given eigenvalue must carry a speci c parity Can this parity be arbitrarily assigned Toeplitz Inverse Eigenvalue Problems 119 A 3 X 3 Example o M E CB mu m12 m13 M gtlt Mgg gtlt L gtlt gtlt gtlt J ltgt traeeM 0 gt Three free parameters in C o Isospectral subset MC1 A2 A3 A0 1 A0 A0 2 mu 7 t W2 m13 mll A01 ltgt 0 A permutation of integers 1 2 3 0 MC Three ellipses ltgt One circumscribes the other two 0 Check 0f mlg intercepts gt 4 if distinct eigenvalues Of 80mm 2 if multiplicity 2 120 Structured Inverse Eigenvalue Problems distinct eigenvalues symmetric eigenvalues multiple eigenvalues Figure 2 Plots of mu versus mm for MC in C3 0 Each ellipse One parity assignment among eigenval ues 0 Wrong assignment gt No Toeplitz o Magnitude of eigenvalues gt Solvability o Ordered eigenvalues alternate in parity Safeguard Toeplitz Inverse Eigenvalue Problems 121 Inverse Problem for Oentrosymmetrie Matrices 0 Close form solution ltgt Given arbitrary D Diagonal matrix A diagZZ1 D Orthogonal matrix Z1 E ngngJ D Orthogonal matrix Z2 6 nglxlgl ltgt Then the matrix 2 0 Z 0 T MKT 1 Z2A 1 Z2 K D ls centrosymmetric D A1 AEJ Odd eigenvalues of M D XEH17 fb Even eigenvalues of M D M may not be ToeplitZ 0 Open Question Search for a Toeplitz matrix on the isospectral surface MCZZ1 MC M E eigenvalues A AZ 122 Structured Inverse Eigenvalue Problems Existence o Solvability has been a challenge ltgt rt equations in TL unknowns ltgt rt 2 5 is analytically intractable ltgt Symmetric Toeplitz matrices can have arbitrary real spectra 226 D Thus far it is a nonconstructiye proof by topo logical degree argument D Open Question Any algebraic proof of existence ltgt Eigenvalues cannot have arbitrary parity Toeplitz Inverse Eigenvalue Problems 123 Idea in Landau s Proof o A matrix Tcl 6 is regularif every principal sub matrix Tcl ck 1 g k g n has the properties ltgt Distinct eigenvalues ltgt Alternate parity With the largest one having even parity 0 Assume the given eigenvalues 1 g 3 An are cen tered ie 2271 Z 0 ltgt Suf ces to solve the TOIEP for matrices of the form T01t3 tn ltgt Necessarily 1 lt 0 0 Consider the map 053 tn 32 yn1 0y ii2 n i ltgtaTO1t3 tn 1 An 124 Structured Inverse Eigenvalue Problems 0 The range of qb is the simplex 1 Z2 E gym 1 AI n 39 2127 7y 1M 32 yn 2 2yn 1 S o Landau s approach ltgt The set 7 of regular Toeplitz matrices of the form T01t3 tn is not empty ltgt The map qb restricted to those t3 tn 6 R 2 such that T0 1 t3 tn 6 7 is a surjective rnap onto A ltgt Any 31 g g yn can be shifted and scaled to a unique point in A Toeplitz Inverse Eigenvalue Problems 125 Numerical Methods 0 Mostly done in S ltgt Laurie s Algorithm 227 ltgt Trench s Algorithm 337 ltgt Continuous method 0 The calculation could be limited to the smaller space C ltgt Cayley Transform 119 ltgt Newton s Re nement to Centrosymmetric Structure 126 Structured Inverse Eigenvalue Problems Continuous Method Toeplitz Inverse Eigenvalue Problems 127 Re ned Newton to Centrosyrnrnetrie Structure o A tangent step 0 Lift by approximation 0 Lift by global ordering 0 Lift by local ordering 128 Structured Inverse Eigenvalue Problems A Classical Newton Method o A function f R gt R o The scheme W W ltf ltxlt gtgtgt1fltxlt gtgt o The intercept ltgt 51W The x intercept 0f the tangent line of the graph of f from 1 fa o The lifting ltgt V1 fx 1 The natural lift of the inter cept along the y axis t0 the the graph of f ToepIitz Inverse Eigenvalue Problems 129 An Analogy of the Newton Method 0 Think of ltgt MGM The graph of f ltgt 7 Toeplitz matrices The x axis ltgt Limit the iteration to C o Manifold MC ltgt Parametrization M QAQT7 QK z 6 0amp3 x 003i ltgt Tangent vector TMltMCgt SM MS S Q1 2QT D Si Skew symmetric in RLgJ X 5 S2 Skew symmetric in RW X W 130 Structured Inverse Eigenvalue Problems A Tangent Step 0 Given M V E MC Parity xed ltgt Find SW and 74 for MW VMV MV V T7av1 o Equivalently A l SWA Ago QVTTTV1gtQVgt ZVTKTTV1KTzV ltgt Spectral decomposition QMTMMQM A QW KTzw 0 Key observation T1V1 0 V T KTltrlt1gtgtK 0 TQM gt The system is split in half Toeplitz Inverse Eigenvalue Problems 131 Find the Intercept o The right hand side of the system is linear in My 0 Diagonal elements in the system gt A linear system for 74 Without reference to S WWW ltgt M1 LJ 1w T Fixed parity 0 zrbi iElkleLt 1H s 2 la jg z gtZE lZ gtM if g lt 239 g n E 0 KT e39 KT 0 lt J D Z yl i the ith column of the matrix Z12 0 Only length of m g in all yector matrix yector multipli cations 132 Structured Inverse Eigenvalue Problems Compute SW 0 Once Tr 1 is determined off diagonal elments in the system gt S zVTlTV1ZV n SltVilt11 1971 Z ltj j lt 1 3 Q Q5 l2l y AWEswish n Slt ZZ 1 zltj 2 J wj 2 ltgt Eigenvalues Within each parity group must be dis tinct ltgt A1 An need not be totally distinct o In case of multiple eigenvalues ltgt Basis of eigenspace splits as evenly as possible be tween symmetric and skew symmetric eigenvectors 113 ltgt Multiplicity of each eigenvalue 3 2 can be formu lated Toeplitz Inverse Eigenvalue Problems 133 Find the Lift o Coordinate free lift Friedland 87 Chu 92 gtTQltVgtT ltgt Lift by approximation so so 1 V R 1 2 2 o In calculation only need T MV1 QVRV MVQVRVQV Zltu1gt gouge ltgt All matrices involved are 2 block diagonal o Quadratic convergence Multiplicity gt 2 2 No SW 2 No 111 0 Can we bypass S to perform a lift 134 Structured Inverse Eigenvalue Problems Lift by Global Ordering o Idea ltgt Look for matrix M W1 6 MC that is nearest to T7au139 1m by global ordering tangent Tv1 V Tn V1 Figure 3 Geometry of Lift by Global Ordering Toeplitz Inverse Eigenvalue Problems 135 0 Answer Wielandt Hoffrnan theorem ltgt Spectral decomposition of Tr 1 is easy V 1 ZltVDTITTV1KTZV1 A1 0 V1 0 A2 ltgt Rearrange A1 An in the same ordering as in KEVH and EMU to obtain MVH and Ag ltgt De ne N V1 T V V1 A 0 u1 Mlt 1 KTZ 1 N W1 K 0 A2 0 New starting point NW1 0 i Hi i 1 A i A 39i 0 Agy1 7 Zea 7WD 0 Signi cance ltgt Parity assignment may be changed ltgt No SW is needed ltgt Multiple eigenvalues with same parity can be han dled 136 Structured Inverse Eigenvalue Problems Lift by Local Ordering 0 Would like to avoid computing SW as well as parity switching o Idea ltgt A is kept xed ltgt Reorganize columns of iiyll and Z3 0 Calculation ltgt Elements in K V1KVD are in the same ordering as those in A1 and A2 0 New starting point Z W1 The reorganized ZWH 0 Global ordering Local ordering when reaching con vergence o Quadratic convergence ltgt Order of convergence order projectionorder tangent step Traub Toeplitz Inverse Eigenvalue Problems 137 Numerical Experiment 0 Example 1 Wrong parity 0 Example 2 Quadratic convergence 0 Example 3 Multiplicity 2 0 Example 4 Multiplicity 3 0 Example 5 High order case 138 Structured Inverse Eigenvalue Problems Example 1 Wrong Parity 0 Test data Wrong parity 1 24128 gtlt100E 2 26407 gtlt 101E Wrong parity A3 26769 gtlt 1000 Lift by Local Ordering Lift by Approximation 2 1 0 1 2 2 1 0 1 2 Lift by Global Ordering Figure 4 Behaviors of Algorithms When Starting with the Wrong Orbit Toeplitz Inverse Eigenvalue Problems 139 0 Lift by approximation gt Staying on the wrong orbit 0 Local ordering gt Wrong orbit Clustering 0 Global ordering gt Change orbit convergence 140 Structured Inverse Eigenvalue Problems Example 2 Quadratic Convergence 0 Limit point 7 may be away from original 743 even if rm 74799 0 Limit points may be different among methods even with the same starting 740 o Eigenvalues of Tr those of Tr but parity may change in the global ordering case Toeplitz Inverse Eigenvalue Problems Case a Case b Case 0 rltgt 0 0 0 20413gtlt103 92349gtlt101 33671gtlt10 1 16065x100 70499gtlt102 41523x10 1 Original Value 84765x10 1 14789x10 1 15578x100 26810x10 1 55709gtlt101 24443gtlt100 H0 0 0 0 28351gtlt10 1 18024gtlt100 63658x10 1 93953x10 1 73881x10 1 40318x10 1 Initial Value 82068x10 1 15694x10 1 10901x100 10634x100 52451gtlt101 32628x100 W 20426x10 16 22204x10 16 74940x10 16 20413gtlt103 92349gtlt101 35391gtlt101 16065x100 70499gtlt102 43645x10 1 Local Ordering 84765x10 1 14789x10 1 15244x100 26810x10 1 55709gtlt101 24655gtlt100 M 86831x10 16 0 47184x10 16 20413gtlt103 92349gtlt101 33671gtlt10 1 16065x100 70499gtlt102 41523x10 1 Approximation 84765x10 1 14789x10 1 15578x100 26810x10 1 55709gtlt10 1 24443gtlt100 W 24113x10 16 11102gtlt1016 61062x10 16 93778gtlt10 2 92646gtlt10 1 35391x10 1 15174x100 61419gtlt10 2 43645x10 1 Global Ordering 99597x10 1 13518x10 1 15244gtlt100 57042x10 1 54694gtlt10 1 24655gtlt100 Table 1 Initial and Final Values of Hquot for Example 2 141 142 Structured Inverse Eigenvalue Problems Iterations Local Ordering Approximation Global Ordering 0 13847x 100 13847x 100 12194x 100 1 71545 x 101 71545 x 101 42739x 101 2 21982 x 102 63866x 102 14179x 102 3 51223x 105 20606x 104 43624x 105 4 44931 x 1010 71037x 109 47985 x 1010 5 14729x 1015 29671 x 1015 17659x 1015 Table 2 Errors of Eigenvalues for Case a in Example 2 Toeplitz Inverse Eigenvalue Problems 143 Example 3 Multiplicity 2 0 Test data Random number 58942 X 101 E 18565 X 101 O 18565 X 101 E 37508 X 101 0 58564 X 101 E 0 Parity unknown ltgt Assume the possibly safest assignment 0 Multiply eigenvalues split between panties o Quadratic convergence 144 Figure 5 Structured Inverse Eigenvalue Problems o Local Ordering Approximation Global Ordering Log of Error of Eigenvalues 10 10 103916 I i I I I 5 15 25 30 Number of Iteration Number of Iteration versus Logarithmic Scale of Errors in Example 3 Toeplitz Inverse Eigenvalue Problems 145 Example 4 Multiplicity 3 0 Test data 84328 X 101 E 12863 X 101 0 12863 X 101 E 12863 X 101 0 12292 X 100 E 0 Lift by approximation fails 0 Methods by local and global ordering converge to 2204x10 1642222x10 112863x10 1742222x10 112863x10 1 with error history 20327 X 100 40355 X 10 2 13903 X 10 4 35477 X 10 9 78896 gtlt 10 16 146 Example 5 Structured Inverse Eigenvalue Problems n20 0 Test data 10242gtlt101 96736gtlt100 21786x100 87090x100 55692x10 1 63594x100 10416x101 94352gtlt100 26374x100 92230x100 63996x10 1 62222x10 b0 55608x100 22651x100 33867x100 40016x100 47955x100 77180gtlt10 1 44879x100 47572x100 ltgt Not the safest possible parity assignment rst ten odd last ten even 0 Method of approximation fails after 100 iterations 0 Method of global ordering performs best ToepIitz Inverse Eigenvalue Problems Figure 6 o Local Ordering Approximation Global Ordering Log of Error of Eigenvalues I 60 100 120 Number of Iteration Number of Iteration versus Logarithmic Scale of Errors in Example 5 147 148 Structured Inverse Eigenvalue Problems Conclusion 0 Solving the TOIEP Within the subspace C71 is possible ltgt Problem size and cost are halved ltgt Multiple eigenvalue case can be handled o Coordinate free Newton like methods are available ltgt Quadratic convergence is observed 0 Parity assignment of eigenvalues plays an important role in whether an TOIEP is solvable 0 Both local and global ordering based on the Wielandt Hoflman theorem7 permit a new way of lifting ltgt Higher multiplicity eigenvalue case can now be han dled Nonnegative Inverse Eigenvalue Problem 149 Nonnegative Inverse Eigenvalue Problem 0 Overview 0 Some Existence Results 0 Symmetric Nonnegative Inverse Eigenvalue Problem 0 Numerical methods 150 Structured Inverse Eigenvalue Problems Overview 0 Many discussions in the literature on the subject 26 30 45 130 1401 143 245 262 109 318 0 Most discussions center around establishing a suf cient or necessary condition to qualify Whether a given set of values is the spectrum of a nonnegative matrix 0 Open Question Which sets of 71 real numbers occur as the spectrum of a nonnegative matrix 0 Open Question Which sets of 71 real numbers occur as the spectrum of a symmetric nonnegative matrix 0 Open Question Very few numerical algorithms Nonnegative Inverse Eigenvalue Problem 151 Some Existence Results 0 Suppose AZZ1 are eigenvalues of an n X n nonnega tiye matrix The the moments TL st 2W 1 must satisfy 821 g 71m 18km for all k m 12 o The set AZZ1 C C is the nonzero spectrum of a strictly positive matrix of size m 2 n if and only if ltgt A gt for all 2 gt 1 oskgt0forallk12 and ltgt The polynomial H1t A has real coef cients 152 Structured Inverse Eigenvalue Problems Symmetric Nonnegative Inverse Eigenvalue Problem c There exist real numbers AZZ1 that occur as the spectrum of a nonnegative n X ii matrix but do not occur as the spectrum of a symmetric nonnegative n X 71 matrix o The symmetric nonnegative inverse eigenvalue problem can be formulated as a constrained optimization prob lem of minimizing the objective function We R HQTAQ R 0 RH subject to Q R E 9n gtlt o For nonsymmetric nonnegative inverse eigenvalue prob lems see the discussion for the stochastic inverse eigen value problems Nonnegative Inverse Eigenvalue Problem 153 Numerical Method o A dynamical system resulting from projected gradient ow can be formulated as T4 dX X X Y 6 al a ll 43 X Y ltgt Xt QtTQt is an isospectral matrix ltgt Yt trix Rt o Rt is a symmetric nonnegative ma 154 Structured Inverse Eigenvalue Problems Stochastic Inverse Eigenvalue Problem 0 General View 0 Karpelevic s Theorem 0 Relationship to Nonnegative Matrices 0 Basic Formulation o Steepest Descent Flow 0 ASVD Flow 0 Convergence 0 Numerical Experiment 0 Conclusion Stochastic Inverse Eigenvalue Problem 155 General View 0 Construct a stochastic matrix With prescribed spec trum ltgt Stochastic structure ltgt No strings of symmetry ltgt Eigenvalues can appear in complex conjugate pairs 0 A hard problem 215 262 ltgt The set 9n of points in the complex plane that are eigenvalues of stochastic n X n matrices is completely characterized ltgt The Karpelevic theorem characterizes only one com plex value a time and does not provide further in sights into When two or more points in 9 are eigen values of the same stochastic matrix 156 Structured Inverse Eigenvalue Problems Karpelevic s Theorem o A number is an eigenvalue for a stochastic matrix if and only if it belongs to a region 9 ltgt Region is symmetric about the real axis ltgt The points on the unit circles are given by emub Where a and b range over all integers such that 0 g a lt b g n ltgt The boundary of 9n consists of curvilinear arcs con necting these points in circular order These arcs are characterized by speci c parametric equations MAP t 1 t73 Ab td 1 75qu7 Where 0 g t g 1 and b dp q 7 are natural integers determined certain speci c rules explicitly given in 7215 262 o The region 94 is shown in Figure 7 Stochastic Inverse Eigenvalue Problem Figure 7 94 by the Karpelevi Theorem 157 158 Structured Inverse Eigenvalue Problems Relation to Normegative Matrices o A complex nonzero number or is an eigenvalue of a non negative matrix with a positive maximal eigenvalue 7 if and only if 057 is an eigenvalue of a stochastic matrix 0 Key transformation ltgt Suppose A is a nonnegative matrix with positive maximal eigenvalue 7 and a positive maximal eigen vector x ltgt Then D 1F1AD is a stochastic matrix Where D diag11 xn o The nonnegative inverse eigenvalue probelm NIEP has been discussed earlier ltgt Some necessary and a few suf cient conditions for the NIEP are available BO ltgt A continuous method for the symmetric NIEP can be formulated 74 ltgt Open Question Need a numerical algorithm for gen eral NIEP Stochastic Inverse Eigenvalue Problem 159 Basic Formulation 0 Notation MM PAP 1 1j E Rnxn is nonsingular 7TRZ B 0 BB 6 Rnxn ltgt A real valued matrix carrying the spectrum infor mation ltgt 0 Hadamard product 0 Idea ltgt Find the intersection of M and 7TR ltgt The intersection if exists results in a nonnegatiye matrix isospectral to A ltgt Reduce the nonnegatiye matrix if its maximal eigen yector is positive to a stochastic matrix by diagonal similarity transformation 160 Structured Inverse Eigenvalue Problems Reformulation 1 Minimize FP R iHPJP l R 0 RH2 Subject to P E Gln R E gln o P and R are used as coordinates to maneuver elements in MM and 7TRZ to reduce the objective value c Feasible domains are open sets 0 A minimum may not exist Stochastic Inverse Eigenvalue Problem 161 Gradient of F 0 Inner product in the product topology ltltX17 31 X27 ltX17 X2gt lt317 0 With respect to the product topology VFP R WP RgtMltPgtT M ltPgtTAltR EDP T 2AP R o R ltgt Abbreviation RIP 1 AP R MP R o R E 9 H 162 Structured Inverse Eigenvalue Problems Steepest Descent Flow o Steepest descent ow Liz MPTAPRPT dB 2A P R R dt 7 O 0 Advantages ltgt No longer need the projection of VFP R as does in the symmetric case ltgt The zero structure in the original matrix R0 is pre served throughout the integration 7 may be used to explore the possibility of constructing a Markov chain with prescribed linkages and spectrum 0 Disadvantage ltgt The solution ow Pt is susceptible to becoming unbounded 7 a possible frailty ltgt The involvement of P 1 is somewhat worrisome Stochastic Inverse Eigenvalue Problem 163 ASVD ow 0 An analytic singular value decomposition of the path of matrices P05 is an analytic path of factorizations Pt X tStY tT Where X t and Yt are orthogonal and S t is diag onal 0 An ASVD exists if Pt is analytic 345 0 The fact that Pt de ned by the differential system is analytic follows from the Cauchy Kovaleyskaya theo rem since the coef cients of the vector eld are analytic 164 Structured Inverse Eigenvalue Problems New Coordinate System o The two matrices P and R are used respectively as coordinates to describe the isospectral matrices and nonnegative matrices ltgt May have used more dimensions of variables than necessary 7 does no harm ltgt When ows Pt and Rt are introduced in a sense a ow in MM and a ow in 7TRZ are also intro duced o The motion of the coordinate P is further described by three other variables X S and Y according to the ASVD c To produce the steepest descent ow a coordinate sys tem X05 St Yt Rt is eventually imposed on matrices in M X 7TRZ Stochastic Inverse Eigenvalue Problem 165 Calculating the ASVD o Differentiate Pt X tStY tT Wright 92 P XSYT XSYT XSYT XTPY SSSQLVTI7 ltgt Z W are skew syrnrnetric matrices 0 De ne Q XTPY ltgt Q is known since P is already speci ed ltgt The inverse of Pt is calculated from P 1 Ys lXT ltgt The diagonal entries of S diag81 3 pro vide us with information about the proximity of P t to singularity 166 0 Flow for St Structured Inverse Eigenvalue Problems magma 0 Obtain Wt and Zt ij ijSk Sjwjka ij ltgt If 3 y 8 then ijsj39 skwjk SkCljk 3ijj jk 3 s 7 339 I s I wle jg 8ij k for allj gt k 0 Flow for Xt and Yt dX XZ all YW dt 0 The ow is now ready to be integrated by any IVP solvers Stochastic Inverse Eigenvalue Problem 167 Convergence o The approach fails only when ltgt Pt becomes singular in nite time 7 requires a restart ltgt F Phi Rt converges to a nonzero constant 7 a LS local solution is found 0 Gradient ows enjoy global convergence ltgt Gt F Pt Rt enjoys the property dG E HVFPt7 Rtll2 S 0 along any solution curve Pt Rt ltgt Suppose Pt rernains nonsingular Then Gt con verges 168 Structured Inverse Eigenvalue Problems Numerical Experiment o Integrator MAT LAB ODE SUITE ltgt 0de113 ABM PECE non stiff system ltgt 0de15s Klopfenstein Shampine quasi constant step size stiff system 0 Stopping criteria ltgt ABSERR RELERR 10 12 ltgt HAP g 10 9 gt a stochastic matrix has been found ltgt Relative improvement of AP R between two con secutive output points 3 10 9 gt a LS solution is found Stochastic Inverse Eigenvalue Problem 169 Example 1 0 Spectrum 10000 02403 01186 i 01805Z 01018 0 Initial values 02002 04213 09229 07243 04548 06964 00752 09361 02235 00981 PO 07538 03620 02157 05272 02637 04366 03220 08688 01729 08697 08897 01436 07097 05343 07837J R0 83281 0 Limit point 01679 00522 04721 00000 03078 01436 01779 04186 01901 00698 B 00000 01377 05291 03034 00299 I 00560 04690 02404 00038 02309 I 01931 01011 05339 01553 00165J 170 Structured Inverse Eigenvalue Problems Distance between Isospectral and Nonnegative Iog FP R 3 0 3909 Figure 8 A log log plot of FPt7Rt versus t for Example 1 Stochastic Inverse Eigenvalue Problem 171 0 Both solvers work reasonably ltgt 0de15s advances with larger step sizes at the cost of solving implicit algebraic equations ltgt J acobians are calculated by nite difference Func tion calls could be reduced by fewer output points 0 Different initial values lead to different stochastic rna trices 172 Structured Inverse Eigenvalue Problems Example 2 0 Spectrum 10000 02608 05046 06438 04483 0 Looking for a Markov Chain with ring linkage ie each state is linked at most to its two immediate neighbors Stochastic Inverse Eigenvalue Problem 173 0 Initial values 01825 07922 02567 09260 09063 01967 05737 07206 05153 00186 PO 05281 02994 09550 06994 01383 07948 06379 05787 01005 09024 05094 08956 03954 06125 04410J 0 Limit point 00000 03094 0 0 06906 00040 05063 04896 0 0 D 0 00000 05134 04866 0 0 0 07733 02240 00021J R0 09210 HOOl H 100 110 111 011 001 r tr thCDr t 04149 0 0 03900 01951 174 Structured Inverse Eigenvalue Problems Example 3 0 Spectrum 10000 02403 03090 i 050000 01018 0 Initial values same as Example 1 or modify R0 0 Slow convergence 03818 00000 04568 00000 01614 05082 03314 00871 00049 00684 E 00000 00000 05288 04712 00000 00266 07634 00292 00310 01498 05416 00524 03835 00196 00029 0323 0 04684 0 0207939 04742 03184 01303 00007 00764 F 0 00000 05231 04769 0 00066 07536 00372 00958 01068 05441 00429 03959 00022 00149 Stochastic Inverse Eigenvalue Problem 175 Conclusion o The theory of solvability on the StlEP or the NIEP is yet to be developed 0 An ODE approach capable of solving the StlEP or the NIEP numerically if the prescribed spectrum is feasi ble is proposed 0 The method is easy to implement by existing ODE solvers o The method can also be used to approximate least squares solutions or linearly structured matrices Structured Inverse Eigenvalue Problems Number of Steps Taken per Interval of Length 10 I I I I I I 35 I o ode113 3 oode155 E 2257 e m V 0 g 3 s 2 o o 0 00 0000 15 o o 39 00000 00000 000 00 0000 00 1 I I I I I I I 0 50 100 150 200 250 300 350 400 450 t Figure 9 A comparison of steps taken by 0de113 and 0de15s for Example 1 Distance between lsospectral and Nonnegative quot39quot1 Wv logDeltaPR Figure 10 A log log plot of FPt7Rt versus t for Example 3 Unitary Inverse Eigenvalue Problem 177 Unitary Inverse Eigenvalue Problem 0 Overview 0 Formulation 0 Existence Theory 178 Structured Inverse Eigenvalue Problems Overview o Eigenvalue of unitary matrices are on the unit circle 0 Suf ces to concentrate on unitary Hessenberg matrices c Any upper Hessenberg unitary matrix H with positive subdiagonal entries can uniquely expressed as the prod uct H 1071 Gn 177n 1Gn77n7 onkECWith 177M lt1f0r1 l ltnand 17711 1 ltgt Each kak k 1 n 1 is a Givens rotation 1 1 GM 2 In k1 J W1th Ck I V 1 ltgt 1107 diagln1 77n 0 Each upper Hessenbergunitary matrix is determined by 271 1 real parameters ltgt 77k1 are called the Schur parameters ltgtH H771 nn Unitary Inverse Eigenvalue Problem 179 Formulation o The Schur parametrization of an upper Hesserberg uni tary matrix requies 2n 1 pieces of information ltgt The complementary parameters Ck j are the sub diagonal elements of H and cannot be independently given 0 Upper Hessenberg unitary matrices With positive sub diagonal entries are related to orthogonal polynomials on the unit circle ltgt Jacobi matrices are related to orthogonal polynomi als on an interval ltgt There should considerably similarity between uni tary inverse eigenvalue problems the Jacobi inverse eigenvalue problems 0 Need a concept for modi ed principal submatrices of H Structured Inverse Eigenvalue Problems 180 Existence Theory o Analogue of SIEP8 ltgt Given D TWO sets AZZ1 and a z strictly interlaced on the unit circle ltgt Then there exist a unique H H 771 a unique or E C of unit modulus such that gt 0H A3221 gt 0H0m17 7067771 HZZ1 o Analogue of SIEP6a 4 771 and ltgt Given D TWO sets AZZ1 and a g strictly interlaced on the unit circle ltgt Then there exist a unique H H 771 that D 0H A3221 D 0ltH7717 39 77771 27 pn l 7711 1107771 pn l 1 O n lnn 77 such Inverse Eigenvalue Problems With Prescribed Entries 181 Inverse Eigenvalue Problems with Prescribed Entries 0 Overview 0 Prescribed Entries Along the Diagonal o Prescribed Entries at Arbitrary Location 0 Numerical Methods 182 Structured Inverse Eigenvalue Problems Overview o The PEIEP is a special kind of matrix completion prob lem 217 ltgt Given D A certain subset IC 2 jtf1 of pairs of sub scripts D A certain set of values G1 ak C F D Another set of n values AZZ1 ltgt Find a matrix X 6 FM such that gt 000 Az1 DX t7jtatf0rt1 k 0 Positions that do not belong to C are free whose 712 16 entries are to be determined ltgt Jacobi structure is a special case ltgt Sometimes only need to ll 1C positions with pre scribed values but not in any speci c order 0 What is the minimal maximal count of k for the prob lem to make sense Inverse Eigenvalue Problems With Prescribed Entries 183 Prescribed Entries along the Diagonal o Schur Horn Theorem on Hermitain matrices o Mirsky Theorem on general matrices o Sing Thompson Theorem on singular values 0 de Oliveira Theorem on general diagonals 184 Structured Inverse Eigenvalue Problems Schur Horn Theorem o Concerns with the relationship between diagonal entries and eigenvalues of a Hermitian matrix 0 The vector a E R is said to majorize A E R if7 assuming the ordering ah Sajn Am 3 gAmn the following relationships hold is k ZAW g 2 for k 1n 711 211 2 Ami Zak 2391 2391 o A Hermitian matrix H with eigenvalues A and diagonal entries a exists if and only if a majom39zes A o The proof for the suf cient part is the hard part ltgt SHIEP Construct such a Hermitian matrix with given diagonals a and eigenvalues A if a majorizes 78 379 Inverse Eigenvalue Problems With Prescribed Entries 185 Mirsky Theorem o Is there any similar connection between eigenvalues and diagonal entries of a general matrix 0 A matrix with eigenvalues 1 An and main diago nal elements a1 an exists if and only if n n 2391 2391 ltgt Not an interesting inverse eigenvalue problems 186 Structured Inverse Eigenvalue Problems Sing Thompson Theorem o Concerns with the relationship singular values and di agonal entries of a general matrix 0 Given vectors d s E R ltgt Assume 81 282 MM 2 MM 3 2 2 dnl ltgt A real matrix with singular values 8 and main diag onal entries d possibly in different order exists if and only if k k S 28 for 191 n 11 2391 71 1 71 1 2 g 8i 8n i1 2391 o STISVP Construct such a square matrix with given diagonals and singular values lTl Inverse Eigenvalue Problems With Prescribed Entries 187 de Oliveira Theorem 0 Corresponding to a given permutation p the set D Z is called a p diagonal ltgt Let p p1 p5 be the representation of p as the product of disjoint cycles pk o A generalizaton of the Mirsky Theorem 105 106 107 ltgt Given D Arbitrary AZZ1 C F D Arbitrary numbers G1 an C F D Suppose that at least one of the cycles p1 p5 has length gt 2 ltgt Then there exists a matrix X 6 FM such that gt M arra D me aiforz 1n 188 Structured Inverse Eigenvalue Problems Prescribed Entries at Arbitrary Locations o London Mine Theorem 246 105 ltgt Given D Arbitrary AZZ1 C F D Arbitrary values a1 an1 D Arbitrary but distinct positions 2 jt11 ltgt There exists a matrix X 6 FM such that D 0X AZZ139 DX t7jtatfort1n 1 0 Can matrices have arbitrary 71 1 prescribed entries and prescribed characteristic polynomials See 116 217 0 Open Question HOW many more entries of a matrix can be speci ed with prescribed eigenvalues Inverse Eigenvalue Problems With Prescribed Entries 189 Cardinality and Locations 0 Speci c locations ltgt Both the SHIEP and the STISVP have n prescribed entries that are located at the diagonal D Certain inequalities involving the prescribed eigen values and diagonal entries must be satis ed ltgt The AIEP has n2 n prescribed entries that are located at the off diagonal D The AIEP is always solvable over an algebraically closed eld and there at most 71 solutions 0 Arbitrary locations With llCl n 217 ltgt Suppose that D F is algebraically closed D The Mirsky condition is satis ed if C 21 D ai j for some j iflC z jt1 and at 0 for all jt y 2 ltgt Then the PEIPE is solvable via rational algorithm over F 190 Structured Inverse Eigenvalue Problems 0 Arbitrary location with llCl 2n 3 191 ltgt Suppose that D F is algebraically Closed D The Mirsky condition is satis ed if C 2 21 D ai j for somej iflC 2 Zyjtb1 and at 0 for all jt y 2 ltgt Then the PEIEP is solvable in F Inverse Eigenvalue Problems With Prescribed Entries 191 Numerical Methods 0 Projected gradient method can be applied 0 An induction proof can be implemented as a recursive algorithm provided the computer permits a subpro gram to invoke itself recursively ltgt Fast recursive algorithms have been proposed for in verse problem associated with the SHIEP and the ST lSVP Theorem ltgt Details are similar to discussion for the inverse sin gular eigenvalue problem 0 Open Question Has not seen the numerical implemen tation of either the de Oliveira Theorem or the London llinc Theorem though this could be done in nitely many steps 0 Open Question Need an algorithm to implement the Hershkowitz results 192 Structured Inverse Eigenvalue Problems Inverse Singular Value Problems o IEP versus ISVP 0 Existence Question 0 A Continuous Approach 0 An Iterative Method for IEP 0 An Iterative Approach for ISVP Inverse Singular Value Problems 193 IEP versus ISVP o Inverse Eigenvalue Problem IEP ltgt Given D Symmetric matrices A0 A1 An E Rm D Real numbers A Z 2 AZ ltgt Find D Values OfC 61 CnT E R D Eigenvalues of the matrix AC A0 0111 6114 are precisely AT L 194 Structured Inverse Eigenvalue Problems 0 Inverse Singular Value Problem ISVP ltgt Given D General matrices B0 B1 Bn 6 Rm m 2 n D Nonnegative real numbers 01 Z Z 0 ltgt Find D Values ofc 01 CnT E R D Singular values of the matrix BltCgt 2 B0 61B1 Jr Can are precisely 0f ajfb Inverse Singular Value Problems 195 Existence Question 0 Not always does the IEP have a solution 0 Inverse Toeplitz Eigenvalue Problem ITEP ltgt A special case of the IEP where A0 0 and Ak All with All 1 ifli jlk 1 W 0 otherwise ltgt Symmetric Toeplitz matrices can have arbitrary real spectra 226 0 Not aware of any result concerning the existence ques tion for ISVP 196 Structured Inverse Eigenvalue Problems Notation 0 C71 All orthogonal matrices in Rm 0 Z EM A diagonal matrix in Rm 2 ofif1 z39j n Z 397 0 otherwise 0 MAX UZVTlU E 9m V E ltgt Contains all matrices in Rm Whose singular values are precisely of 0 o B BClc E R 0 Solving the ISVP E Finding an intersection of the two sets MAE and B Inverse Singular Value Problems 197 A Continuous Approach oAssume ltgtltB0Bkgt0for1 k n o The projection of X onto the linear subspace spanned byB1 Bn TL PltXgt BX BigtBi k1 o The distance from X to the af ne subspace B distX B HX B0 0 De ne for any U E Rmxm and V 6 RM a residual matrix RU V UZVT B0 PUZVT 0 Consider the optimization problem Minimize FU V HRU m2 Subject to U V E 9m gtlt 198 Structured Inverse Eigenvalue Problems Compute the Projected Gradient o Frobenius inner product on Ptme gtlt Rm ltA17B17 142732 3 ltA17 A2gtltB17 32gt The gradient VF may be interpreted as the pair of matrices VFU V RU VV2T RU VTU2 o Tangent space can be split 7EU7VOm gtlt 730071 gtlt TVOn 0 Projection is easy because Rm Tvom e9 Tvomi Visual e V802 Inverse Singular Value Problems 199 0 Project the gradient VFU V onto the tangent space TUVOm gtlt OW 9U7 V T T T T RU VVZ U UZV RU V U 2 7 RU VTUZVT VZTUTRU WV 2 o Descent vector eld dU7 V dt de nes a steepest descent ow on the manifold 9m gtlt C71 for the objective function F U V 9U7 V 200 Structured Inverse Eigenvalue Problems The Differential Equation on M3Z 0 De ne Xt UtZVtT o X t satis es the differential system dX i XXTB0 PX Bo PXTX E 2 XBo PXT Bo PXTXX 2 o X t moves on the iso singular value surface MAE in the steepest descent direction to minimize distltX t B o This is a continuous method for the ISVP Inverse Singular Value Problems 201 Remarks o N 0 assumption on the multiplicity of singular values is needed 0 Any tangent vector TX to MAX at a point X E MAE about which a local chart can be de ned must be of the form TX XK HX for some skew symmetric matrices H E Rmxm and K E Rm 202 Structured Inverse Eigenvalue Problems Ari Iterative Approach for ISVP 0 An analogous Newton iteration for PIEP has been dis cussed Assume ltgt Matrices B0 B1 Bn are arbitrary ltgt All singular values of 0 are positive and dis tinct 0 Given X E MAE ltgt There exist U V E 9m and V 6 C71 such that T UV XWVW Z ltgt Seek a B intercept B CV1 of a line that is tangent to the manifold MAE at X V ltgt Lift the matrix BMW 6 B to a point XWH E MAE Inverse Singular Value Problems 203 Find the Intercept 0 Find ltgt Skew symmetric matrices H V E Rmxm and KW E Rm and ltgt A vector CltV1gt E R such that XW XVKV HWXW BCV1 o Equivalently 1 2W W2 U TBC 1V ltgt Underdetermiried skew symmetric matrices Hm UltVgtTHltVgtUltVgt7 Km VltVgtTKltVgtVW 0 Can determine CltV1 H V and KW separately 204 Structured Inverse Eigenvalue Problems 0 Totally mag 1 n unknowns 7 the vector CltV1gt and the skew matrices HM and id 0 Only mn equations 0 Observe Hg 71 1 Z7 j m ltgt W unknowns ltgt Locate at the lower right corner of HM ltgt Are not bound to any equations at all ltgt Set Hg0f0rn1 z 7 j m o Denote We UltVgtTBCltV1gtVltVgt Then W5 Eu SHE Iii2 Inverse Singular Value Problems 205 Determine CltV1gt oForlgz j n JVCV1 0 bV ltgt Know quantities Jet usleBtvgyl for 1 3 875 3 n 0 of 0T bg ugleBovgyl for 1 g s g 71 erg column vectors of U V 1 column vectors of V o The vector CVH is obtained 0 CVH gt WW pUHOJ A19191dm00 AAOU 91 1190191111 911 o 50 40 z z zZ E 652 gt2 MMMDMMMD a dig A930 4 M Liz 5ng XML 4 W W quotde 75521913 M lt if pm g1H 10 8UAOS m AA uS gt2SIHH 25 z 01 jH le m l quSIm wSzSIuxuo 3119 GUIULIGJGG sm9q01d ammua fg QSJQAUI pamqamqs 906 Inverse Singular Value Problems 207 Find the Lift Up 0 De ne orthogonal matrices HM HM I 2 K Sl R 1 0 De ne the lifted matrix on MAE XltV1gt RTXWS 0 Observe Xu1 RT HVBCV1 KVS and RTeHM I 6 KVS In if HHWH and HKWH are small 22 208 Structured Inverse Eigenvalue Problems 0 For computation ltgt Only need orthogonal matrices Uu1 RTUy VWH STVW n1 ltgt Does not need to form X explicitly Inverse Singular Value Problems 209 Quadratic Convergence 0 Measure the discrepancy between U V E Rmxmx BM in the induced Frobenius norm 0 Observe ltgt Suppose D The ISVP has an exact solution at 0 gt svn of Bamp 02V ltgt De ne error matrixcc E E1 E2 U U V V ltgt If UUT eH and VVT eK then UUT E1 UWT eH rm H 0HHH2 and a similar expression for VVT ltgtThus WHJOH 0HEH 210 Structured Inverse Eigenvalue Problems 0 At the V th stage de ne EltVgt E9 E5 UW U W V o How far is U TBCVV away from Z ltgt Write UltVgtTBCVltVgt e H ZeK UW H gtUltugt gltvltugtT K gtVltugt with Hg UltVgtHltVgtUltVgtT7 Kg 7 VltVgtKltVgtVltVgtT7 ltgtThen eHW UltVgtUT eK Ey VWVT ltgt So HltH K H WWW gtlt ltgt Norm invariance under orthogonal transformations gt HI1 K H OWEWD Inverse Singular Value Problems 211 o Rewrite UltVgtTBCVltVgt 2 2de II Z 0HEW H2 0 Compare U TBc Bclt 1gt VW KW W ICIW ltvg 0HE P o Diagonal elements gt JWCquot CW OWEWHQ ltgt Thus H6quot CMlH OWEWHQ o Off diagonal elements gt HEW HWH OWEWHQ WW KWH OWEWHQ ltgt Therefore HltH 7K H OWEWH 0 Together HHW H MW K H 0HEWH2 WM OWEWHQ A 212 Structured Inverse Eigenvalue Problems 0 Observe Eiy1gt UV1 U RTUV H VUV HM I 2 i I Hi 0HH H2 HV 1 2 gt ltI 2 WW gtlt HM HM 0 H VHV HM HH H2 1 7PM ltgt It is Clear now that V 1 V M r H 0ltHElt W o A similar argument works for ESWD 0 We have proved that HEme OWEWHQ Inverse Singular Value Problems 213 Multiple Singular Values 0 Previous de nition in nding the B intercept of a tan gent line of MAE allows ltgt N0 zero singular values ltgt N0 multiple singular values 0 Now assume ltgt All singular values are positive ltgt Only the rst singular value of is multiple with multiplicity p 214 Structured Inverse Eigenvalue Problems 0 Observe ltgt All formulas work except gtF0r1 iltj ponlylltnow Wig W 0 D No values for Illf and Ill3 can be determined D Additional q 1 equations for the vector CltV1gt arise 0 Multiple singular values gives rise to an overdetermined system for CltV1 ltgt Tangent lines from MAE may not intercept the af ne subspace B at all ltgt The ISVP needs to be modi ed Inverse Singular Value Problems 215 Modi ed ISVP 0 Given gtllt ltgt Positive values 01 a gt 0 gt gt 0nq 0 Find ltgt Real values of Cl cn ltgt The n q largest singular values of the matrix matrix BC are 013 0q 216 Structured Inverse Eigenvalue Problems Find the Intercept 0 Use the equation 2 W 1w UltVgtTBltCltvwltvgt to nd the B intercept Where ltgt The diagonal matrix g diag 0q ampnq1 dn ltgt Additional singular values dnq1 6 are free parameters Inverse Singular Value Problems 217 The Algorithm Given U V E 9m and V 6 C71 o Solve for CV from the system of equations T T Z HEV BMW c y 0 um Boum 239 139 a k1 fori1n q T Z ugleBkvgy a Bkvgyl C VH k1 T u TB0u V a Bong for 1 g 8 lt t g p 0 De ne 3 by AM 0 iflglcgn q ultygtTBC 1luV if n klt k k a q lt n 0 Once CltV1gt is determined calculate WW dASI Sql 10 SB XBAA BLUES Sql H 581mm Sq paaoold pauymleqap an H 1 pm WH SOHO o b zwa m fgtdfu3fgtzSIM z M z MWMWWAlfmi w3f231u 1 4 qufEIEWSzSIJFUJI ltlt2V 4 4514 ML 3fgt231 a W Xq paugap 81 WE ltgt degtzSI 0 gw ya m ng fgtdfu3fgt231 z n z a ab a39i aig Xq paugap 81 H 21 ltgt d FgtZ LMOEampWlt 5le pm if augap 01 SBAA 11qu lt 5 11 11 1 4 11 m w rltw w9 m 4 91 pagsms aq 01 1101112an Sq d S f gt Z S I 103 ltgt WH pm 1 89011113111 omawIHs mags augaq o 818 summmd 9nmua g QSJQAUI pamqamqs Inverse Singular Value Problems 219 Remarks o No longer on a xed manifold MAE since i is Changed per step c The algorithm for multiple singular value case con verges quadratically 220 Structured Inverse Eigenvalue Problems Zero Singular Value 0 Zero singular value gt rank de ciency 0 Finding a lower rank matrix in a generic af ne subspace B is intuitively a more dif cult problem 0 More likely the lSVP does not have a solution 0 Consider the simplest case Where of gt gt 011 gt of 0 ltgt Except for Hm and Hm Z 71 1 m all other quantities including CltV1gt are well de ned ltgt It is necessary that M 0forz nim TL ltgt If the necessary condition fails then no tangent line of MAE from the current iterate X V will intersect the af ne subspace B Inverse Singular Value Problems 221 Example of the Continuous Approach o Integrator 7 Subroutine ODE Shampine et al 75 ltgt ABSERR and RELERR 10 12 ltgt Output values examined at interval of 10 0 Two consecutive output points differ by less than 10 10 gt Convergence 0 Stable equilibrium point is not necessarily a solution to the lSVP 0 Change to different initial value X 0 if necessary 222 Structured Inverse Eigenvalue Problems Example of the Iterative Approach 0 Easy implementation by MATLAB ltgt Consider the case when m 5 and n 4 ltgt Randomly generated basis matrices by the Gaussian distribution 0 Numerical experiment meant solely to examine the be havior of quadratic convergence ltgt Randomly generate a vector c E R4 ltgt Singular values of B c used as the prescribed sin gular values ltgt Perturb each entry of c by a uniform distribution between 1 and 1 ltgt Use the perturbed vector as the initial guess Inverse Singular Value Problems 223 Observations o The limit point 0 is not necessary the same as the original vector c o Singular values of B 0 do agree with those of B C 0 Differences between singular values of BMW and B 0 are measured in the 2 norrn o Quadratic convergence is observed 224 Structured Inverse Eigenvalue Problems Example of Multiple Singular Values 0 Construction of an example is not trivial ltgt Same basis matrices as before ltgt Assume p 2 ltgt Prescribed singular values 0 5 5 2T ltgt Initial guess of 00 is searched by trials 0 The order of singular values could be altered ltgt The value 5 is no longer the largest singular value ltgt Unless the initial guess 00 is close enough to an exact solution 0 no reason to expect that the algo rithm will preserve the ordering ltgt Once convergence occurs then 0 must be part of the singular values of the nal matrix 0 At the initial stage the convergence is slow but even tually the rate is picked up and becomes quadratic Inverse SingularEigenvalue Problem 225 Inverse Singualar Eigenvalue Problem 0 Overview 0 A Recursive Algorithm 0 The Matrix Structure 0 Numerical Experiment 226 Structured Inverse Eigenvalue Problems Overview o The Schur Horn Theorem gives the connection between diagonal entries and eigenvalues of a Hermitian matrix 0 The Mirsky Theorem gives a connection between diag onal entries and eigenvalues of a general matrix 0 The Sing Thompson Theorem gives the connection be tween diagonal entries and singular values of a general matrix 0 What is the connection between singular values and eigenvalues of a matrix ltgt singular value leigenvaluel if Hermitian matrices ltgt How about general matrices 0 Can we create matrices with prescribed singular values and eigenvalues ltgt Desirable for test matrices Inverse SingularEigenvalue Problem 227 Weyl Horn Theorem 0 Given vectors E C and or E R ltgt Assume W Z Z Wt C161 2 Z Or ltgt Then a matrix with eigenvalues 1 An and sin gular values 051 ozn exists if and only if H k k EHOdj ki17 L 1 j1 HlVl 0639 j1 m m H 3 H H m D If Mnl gt 0 then logoz majorizes log o How to solve the inverse singular eigenvalue problem numerically 228 Structured Inverse Eigenvalue Problems A Recursive Algorithm o The Building Block 7 2 X 2 Case 0 The Original Proof by Induction 0 An Innocent Mistake 0 A Recursive Clause in Programming Inverse SingularEigenvalue Problem 229 The 2 x 2 Case o The Weyl Horn Condition l1l S 0617 051052 062 S l2l S l1l S 061 lA1l2 l2l2 g 05 05 0 The building block 7 A triangular matrix i 1H Alml has singular value 051 042 if and only if u M a M WP ltgt A is complex valued when eigenvalues are complex ltgt A stable way of computing u 07 ifllt061 0622 l1l l2l2lSE l041 0422 l1l Mgl otherwise 230 Structured Inverse Eigenvalue Problems Ideas in Horn s Proof 0 Reduce the original inverse problem to two problems of smaller sizes 0 Problems of smaller sizes are guaranteed to be solvable by the induction hypothesis 0 The subproblems are a xed together by working on a suitable 2 X 2 corner 0 The 2 X 2 problem has an explicit solution Inverse SingularEigenvalue Problem 231 Key to the Algorithmic Success o The eigenvalues and singular values of each of the two subproblems can be derived explicitly 0 Each of the two subproblems can further be down sized o The original problem is divided into subproblems of size 2 X 2 or 1 X 1 o The smaller problems can be conquered to build up the original size 0 In an environment that allows a subprogram to in voke itself recursively only one step of the divide and conquer procedure Will be enough 0 Very similar to the radix 2 FFT gt fast algorithm 232 Structured Inverse Eigenvalue Problems Outline of Proof 0 Suppose 05139 gt 0 for allz 1 n So Z y 0f0r all 2 ltgt The case of zero singular values can be handled in a similar way 0 De ne 03912 O39Z39Z ltgt Assume a minlSZSn1 01 occurs at the index j 0 De ne 051 24 fori2 n 1 o The following three sets of inequalities are true The numbers satisfy the Weyl Horn conditions Mil Z Wily 0 2 p 0amp12 052 2 2 Orj lj1l Z Z lAn il 2 p 06341 Z Z Odn i Z 06n Inverse SingularEigenvalue Problem 233 o By induction hypothesis ltgtThere exist unitary matrices U1 V1 6 CW and triangular matrices A1 such that 0 Eff 0 O U1 72 V1141 0 O04j 39Aj ltgt There exist unitary matrices U2 V2 E Cn jWW 7 and triangular matrix A2 such that armour Mamxx 0 0439 0 0 A X 39 39 n 1gtlt 00quotanJ 00OpJ 234 Structured Inverse Eigenvalue Problems 0 Horn s Claim The block matrix M 0A2 can be permuted to the triangular matrix 2 X X X 39 0 X Aj X 0 0 o 0 0 0 0 p X X X j1 O 0 0 An1 o The 2 X 2 corner can now be glued together by 00 7 i 1u Holoplwolo Ail How to do the permutation or is it a mistake ltgt It takes more than permutation to rearrange the di agonals of a triangular matrix Inverse SingularEigenvalue Problem 235 A MAT LAB Program function Asvdeigalphalambda n lengthalpha if n Z The 1 by 1 case A lambda1 elseif n Z The 2 by 2 case UVA twobytwoalphalambda else Z Check zero singular values tol nalpha1eps k sumalpha gt tol m sumabslambda gt tol if k n X Nonzero singular values j 1 s alpha1 temp s 1 for i 22n temp tempalphaiabslambdai if temp lt s j i s temp end end rho abslambda1lambdans UOVOAO twobytwosrholambda1lambdan IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII llIIIIIIIIIIIIIIIII A1 svdeigalpha1jslambda2j RECURSIVE A2 svdeigalphaj1nlambdaj1n 1rho Z CALLING Z IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII A A1zerosjn jzerosn jjA2 Temp A A1UO11Temp1UO12Tempn AnUO21Temp1UO22Tempn Temp A A1VO11Temp1VO12Tempn AnVO21Temp1VO22Tempn else Z Zero singular values beta prodabslambda1mprodalpha1m 1 U3V3A3 svdeigalpha1m 1betalambda1m A zerosn A1 m1 m V3 A3V3 for i m1k Aii1 alphai end Amm1 sqrtabsalpham 2 beta 2 end end 236 Structured Inverse Eigenvalue Problems Matrix Structure o A Modi ed Proof 0 A Symbolic Example Inverse SingularEigenvalue Problem 237 Correct the Mistake o Horn s requirement ltgt Both intermediate matrices A1 and A2 are upper triangular matrices ltgt Diagonal entries are arranged in a certain order D Valid from the Schur decomposition theorem D More than permutation not easy for computa tion D To rearrange diagonal entries yia unitary similar ity transformations While maintaining the upper triangular structure is expensive 0 Our contribution ltgt The triangular structure is entirely unnecessary ltgt The matrix A produced from our algorithm is gen erally not triangular ltgt Do not need to rearrange the diagonal entries ltgt Modify the rst and the last rows and columns of O the block diagonal matrix A1 as if nothing O A2 happened is enough 238 0 Algorithm ltgt Denote U0 mm and V0 vow ltgt Then 0 0amp1 O O 110711 110712 J U1 0 J 0 a2 0 W O O nil O 0 U2 quot O lik U021 0 U022 0 an is the desired matrix 0 A has the structure 1 gtllt gtllt 2 X 0 0 j1 X 7 X X j A 7 gtllt 0 0 0 Aj1 X gtllt 0 X Aj2 O 0 gtllt gtIlt l A Structured Inverse Eigenvalue Problems 710711 0 710712 0 111 0 710721 0 710722 6969 ltgt gtlt unchanged original entries from A1 or A2 ltgt entries of A1 or A2 that are modi ed by scalar rnultiplications ltgt gtllt possible new entries that were originally zero y Inverse SingularEigenvalue Problem 239 A Variation of Horn s Proof 0 Does the algorithm really works ltgt Clearly A has singular values 041 an ltgt Need to show that A has eigenvalues A1 An 0 What has been changed P1 Diagonal entries of A1 and A2 are in xed orders 0 2 j and A341 n1 p respectively P2 Each A is similar through perrnutations which need not to be known to a lower triangular matrix whose diagonal entries constitute the same set as the diag onal entries of A Thus each A has precisely its own diagonal entries as its eigenvalues P3 The rst row and the last row have the same zero pattern except that the lower left corner is always zero P4 The rst column and the last column have the same zero pattern except that the lower left corner is al ways zero 0 Use graph theory to show that the af xed matrix A has exactly the same properties 240 Structured Inverse Eigenvalue Problems A Symbolic Example o Dividing process 1 2 3 A4 5 A6 051 052 053 054 055 055 1 5 5 91 U 01 p1 0391 2 3 4 5 p1 051 052 053 054 055 056 0391 5 2 J2 U 02 W 02 2 3 4 P2 061 062 063 064 055 53 1 u g 03 4 03 053 054 055 241 Inverse SingularEigenvalue Problem 0 Conquering process 00A6 0xxmo 4 OOOAOO OOMXOO 2 A00X M0 00 J 91 0000011 OxxNoO OOMOO 00x0 3 0A x00 XMOOXO UOXXOO 11 0 No OOOMO OOMXO M00 1 000 x000 02 000 0A2 0 x 00A gtlt 00XA4 0000p2 TT 122 0 3 p 0 0 4 023 A0 a 0 0M0 Mo0 3 U 1 0 242 Structured Inverse Eigenvalue Problems Numerical Experiment o The divide and conquer feature brings on fast compu tation o The overall cost is estimated at the order 0f 00 o A numerical simulation Inverse SingularEigenvalue Problem 243 Rosser T est o Rosser matrix R 611 196 7192 407 78 752 749 29 196 899 113 7192 771 743 78 744 7192 113 899 196 61 49 8 52 407 7192 196 611 8 44 59 723 78 771 61 8 411 7599 208 208 752 743 49 44 7599 411 208 208 749 78 8 59 208 208 99 7911 29 744 52 723 208 208 7911 99 ltgt Has one double eigenvalue three nearly equal eigen values one zero eigenvalue two dominant eigenval ues of opposite sign and one small nonzero eigen value ltgt grl e computed eigenvalues and singular values of R 7102004901842999764r03 1020049018429997603 1020049018429997e03 1020049018429996e03 1020000000000000603 1020000000000000603 A 1019901951359278603 a 1019901951359279603 1000000000000001e03 7 1000000000000000603 9999999999999998602 9999999999999998602 98048640721526016702 98048640721626726702 48511195060996226713 10546033426670986714 J 244 Structured Inverse Eigenvalue Problems 0 Using the above and or ltgt A nonsyrnrnetric matrix is produced 10200603 0 0 0 0 0 0 0 0 710200603 0 0 0 0 0 0 0 0 102006 03 0 0 0 0 0 0 0 0 10199603 0 0 146686709 0 0 0 0 10000603 0 0 0 0 0 0 10000603 0 0 0 0 0 7152576705 0 0 980496702 0 0 0 0 0 0 0 140456707 0 ltgt The re cornputed eigenvalues and singular values of are 710200490184299976 03 1020049018429997603 1020049018429997603 1020049018429997603 1020000000000000603 1020000000000000603 5 1019901951359278603 0 1019901951359279603 1000000000000001603 7 1000000000000001603 9999999999999998602 9999999999999998602 9804864072157216 02 98048640721626726702 0 0 ltgt The re cornputed eigenvalues and singular values agree With those of R up to the machine accuracy Inverse SingularEigenvalue Problem 245 Wilkinson Test o Wilkinson s matrices ltgt All are symmetric and tridiagonal ltgt Have nearly but not exactly equal eigenvalue pairs 0 Using these data ltgt Discrepancy in eigenvalues and singular values be tween Our constructed matrices and Wilkinson s ma trices ltgt Matrices constructed are nearly but not symmetric 246 Structured Inverse Eigenvalue Problems Conclusion o Weyl Horn Theorem completely characterizes the rela tionship between eigenvalues and singular values of a general matrix 0 The original proof has been modi ed 0 With the aid of programming languages that allow a subprogram to invoke itself recursively an induction proof can be implemented as a recursive algorithm 0 The resulting algorithm is fast The cost of construction is approximately 00 o The matrix being constructed usually is not symmet ric and is complex valued if complex eigenvalues are present 0 Numerical experiment on some very challenging prob lems suggests that our method is quite robust Inverse SingularEigenvalue Problem Minimal Sigular Value ogminimal singular value Figure 11 History of the smallest singular value for Example 3 size of problem Figure 12 log log plot of computational ops versus problem sizes 247 248 Structured Inverse Eigenvalue Problems DisciEpancy m Eigenvaiues and SinguiaiVaiues m disciepancymeigemames m udischpancvinsinuuiavvaiues r gt E 39 o s 7 0 Ni o a E a u 5 0 u o I g a o 5 m 0 o m g o 1 9 o was 2 4 a in 12 m we a SiZE uiWiikmsnn mam Figure 13 L2 norm of discrepancy in eigenvalues and singular values Wilkinson Matrix of Size 21 Figure 14 3 D mesh representation of 21 gtlt 21 matrices

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.