# The Nelder-Mead Simplex Algorithm Is Sixty Years Old: New Convergence Results and Open Questions
## 4 Connections and Properties  
Here, we investigate the connection between the transformation matrices of both algorithms, their consequences and the spectral properties of the matrices. The corresponding transformation matrices of Algorithms 1 and 2 are connected by orthogonal similarities. For any \(1\leq s\leq n+1\),  
\[P^{T}T_{s}(\alpha)P=T_{n+1}(\alpha)=T(\alpha) \tag{17}\]  
with \(P=[e_{1},\ldots,e_{s-1},e_{s+1},\ldots,e_{n+1},e_{s}]\) and  
\[Q^{T}T_{s}^{shr}Q=\frac{1}{2}I+\frac{1}{2}e_{1}e^{T}=T_{shr} \tag{18}\]  
with \(Q=[e_{s},e_{1},\ldots,e_{s-1},e_{s+1},\ldots,e_{n+1}]\). With \(\widetilde{S}^{(k)}=\left[\widetilde{x}_{1}^{(k)},\ldots,\widetilde{x}_{n+1} ^{(k)}\right]\) and \(S^{(k)}=\left[x_{1}^{(k)},\ldots,x_{n+1}^{(k)}\right]\), denote the \(k\)th simplices of Algorithms 1 and 2, respectively. If a permutation matrix \(Q_{k}=\left[e_{r_{1}},\ldots,e_{r_{n+1}}\right]\in\mathbb{R}^{(n+1)\times(n+1)}\) exists such that \(\widetilde{S}^{(k)}Q_{k}=S^{(k)}\), \(x_{1}^{(k)}=\widetilde{x}_{\ell_{k}}^{(k)}\) and \(x_{n+1}^{(k)}=\widetilde{x}_{h_{k}}^{(k)}\), then we can ask if \(\widetilde{S}^{(k+1)}\) and \(S^{(k+1)}\) define the same simplex. The assumption implies that \(e_{r_{1}}=e_{\ell_{k}}\) and \(e_{r_{n+1}}=e_{h_{k}}\). Hence, \(\widetilde{S}^{(k)}=S^{(k)}Q_{k}^{T}\) and  
\[\widetilde{S}^{(k+1)}=\widetilde{S}^{(k)}T_{h_{k}}(\alpha_{k})=S^{(k)}\Big{(}Q _{k}^{T}+\Big{(}Q_{k}^{T}c_{h_{k}}(\alpha_{k})-Q_{k}^{T}e_{h_{k}}\Big{)}e_{h_{ k}}^{T}\Big{)}.\]  
Since \(e_{h_{k}}=Q_{k}e_{n+1}\), \(Q_{k}^{T}e_{h_{k}}=e_{n+1}\) and \(Q_{k}^{T}c_{h_{k}}(\alpha_{k})=\left[e_{r_{1}},\ldots,e_{r_{n+1}}\right]^{T}c_{ h_{k}}(\alpha_{k})=c_{n+1}(\alpha_{k})\), we have  
\[\widetilde{S}^{(k+1)} =S^{(k)}\Big{(}I+(c_{n+1}(\alpha_{k})-e_{n+1})e_{n+1}^{T}\Big{)}Q _{k}^{T}=S^{(k)}T(\alpha_{k})Q_{k}^{T}\] \[=S^{(k+1)}P_{j^{(k)}}^{T}Q_{k}^{T}.\]  
In the case of shrinking,  
\[\widetilde{S}^{(k+1)}=\widetilde{S}^{(k)}T_{\ell_{k}}^{shr}=S^{(k)}\bigg{(} \frac{1}{2}Q_{k}^{T}+\frac{1}{2}Q_{k}^{T}e_{\ell_{k}}e^{T}\bigg{)}.\]  
Note that \(Q_{k}^{T}e_{\ell_{k}}=Q_{k}^{T}Q_{k}e_{1}=e_{1}\). Hence,  
\[\widetilde{S}^{(k+1)}=S^{(k)}\bigg{(}\frac{1}{2}Q_{k}^{T}+\frac{1}{2}e_{1}e^{ T}\bigg{)}=S^{(k)}\bigg{(}\frac{1}{2}I+\frac{1}{2}e_{1}e^{T}Q_{k}\bigg{)}Q_{k}^{T}.\]  
Since \(e^{T}Q_{k}=e^{T}\), we have that  
\[\widetilde{S}^{(k+1)}=S^{(k)}T_{shr}Q_{k}^{T}=S^{(k+1)}\Big{[}P^{(k)}\Big{]}^{T }Q_{k}^{T}.\]  
Hence, the simplices of iteration \(k+1\) are the same for the ordering of vertices. Since the continuation of the original Nelder-Mead method is not uniquely determined, unlike in the case of Algorithm 2, we can expect similar although not identical results for both algorithms. The following results are obvious. For any \(1\leq j\leq n+1\),  
\[T_{j}(\alpha)T_{j}(\beta)=T_{j}(-\alpha\beta).\]  
**Lemma 1**. : _The eigenvalues of \(T_{j}(\alpha)\) are \(\lambda_{i}\big{(}T_{j}(\alpha)\big{)}=1\) (\(i=1,\ldots,n\)) and \(\lambda_{n+1}\big{(}T_{j}(\alpha)\big{)}=-\alpha\) (\(j=1,\ldots,n+1\)). \(T_{j}^{\text{str}}\) has the eigenvalues \(\lambda_{1}\Big{(}T_{j}^{\text{str}}\Big{)}=1\) and \(\lambda_{i}\Big{(}T_{j}^{\text{str}}\Big{)}=\frac{1}{2}\) (\(i=2,\ldots,n+1\)) for \(j=1,\ldots,n+1\). Both \(T_{j}(\alpha)\) and \(T_{j}^{\text{str}}\) have a diagonal Jordan form._  
**Corollary 1**.