# The Nelder-Mead Simplex Algorithm Is Sixty Years Old: New Convergence Results and Open Questions
## 4 Connections and Properties
: _Sequences \(\Big{\{}T_{j}(\alpha)^{k}\Big{\}}_{k=1}^{\infty}\) and \(\bigg{\{}\Big{(}T_{j}^{\text{str}}\Big{)}^{k}\bigg{\}}_{k=1}^{\infty}\) are uniformly bounded for \(|\alpha|\leq 1\) and convergent for \(-1\leq\alpha<1\) (see, e.g., [23; 24; 25])._  
Note that \(\big{\|}T_{j}(\alpha)\big{\|}_{2}=\big{\|}T(\alpha)\big{\|}_{2}=\big{\|}T( \alpha)P_{j}\big{\|}_{2}>1\) and \(\big{\|}T_{j}^{\text{str}}\big{\|}_{2}=\big{\|}T_{\text{str}}\big{\|}_{2}= \big{\|}T_{\text{str}}P\big{\|}_{2}>1\), where  
\[\big{\|}T(\alpha)\big{\|}_{2}=\left(s_{n}+\sqrt{s_{n}^{2}-\alpha^{2}}\right) ^{\frac{1}{2}}\quad\left(s_{n}=\frac{1+\alpha^{2}}{2}+\frac{(1+\alpha)^{2}}{2 n}\right) \tag{19}\]  
and  
\[Q^{T}T_{s}^{shr}Q=\frac{1}{2}I+\frac{1}{2}e_{1}e^{T}=T_{shr} \tag{18}\]0  
The first expression follows from a result on the singular values of companion matrices (see, e.g., [PERSON] [26] or [PERSON] [27]), while the second follows from a result of [PERSON], [PERSON] and [PERSON] [28]. Matrices \(T_{\text{str}}\), \(T_{\text{str}}P\), \(T_{j}^{\text{str}}\), \(T_{j}(\alpha)\), \(T(\alpha)P_{j}\) (\(-1<\alpha<0\)) are left-stochastic. Hence,  
\[Q^{T}T_{s}^{shr}Q=\frac{1}{2}I+\frac{1}{2}e_{1}e^{T}=T_{shr} \tag{18}\]1  
We note that \(T_{j}(1)\) (\(1\leq j\leq n+1\)) is an involution. If \(T(1)\) is multiplied by a permutation matrix \(P_{j}\) (\(1\leq j\leq n\)), this property is lost. However, for \(n=2\), \(T(1)P_{2}\) is a \(6\)-involutory matrix, which is exploited in proving Theorem 3 (for \(k\)-involutory matrices, see [PERSON] [29]). The multiplication of \(T(\alpha)\) or \(T_{\text{str}}\) by a permutation matrix \(P_{j}\) or \(P\) makes a significant change in the eigenstructure. The following results hold (see Theorem 3 and Corollary 1 of [PERSON] [15]). **Theorem 1**. : _(i) \(T(\alpha)P_{1}\) has at least one eigenvalue \(\lambda=1\). (ii) \(T(1)P_{j}\) (\(1\leq j\leq n+1\)) has at least two eigenvalues \(\lambda=1\). (iii) If \(\alpha>-1\) and \(j\geq 2\), then \(T(\alpha)P_{j}\) has exactly \(j-1\) eigenvalues \(\lambda=1\). (iv) For \(|\alpha|<1\), \(T(\alpha)P_{1}\) has exactly one eigenvalue \(\lambda_{1}=1\), while the remaining \(n\) eigenvalues are in the open unit disk. (v) If \(|\alpha|<1\) and \(2\leq j\leq n+1\), then \(T(\alpha)P_{j}\) has exactly \(j-1\) eigenvalues \(\lambda=1\), while \(n+2-j\) eigenvalues are in the open unit disk. (vi) If \(\alpha=1\) and \(1\leq j\leq n+1\), then all the eigenvalues of \(T(1)P_{j}\) are on the unit circle. (vii) If \(\alpha>1\) and \(j=1\), then \(T(\alpha)P_{1}\) has a second eigenvalue in the interval \(\Big{(}1,1+\frac{1+\alpha}{n}\Big{)}\) and all its eigenvalues are in the annulus \(1\leq|\lambda|\leq 1+\alpha\)._  
**Corollary 2**. : _The eigenvalues of \(T_{\text{str}}P\) (\(P\in\mathcal{P}_{n+1}\)) are \(\lambda_{1}(T_{\text{str}}P)=1\) and \(|\lambda_{i}(T_{\text{str}}P)|=\frac{1}{2}\) for \(i=2,\ldots,n+1\)._  
The change in the eigenstructure of \(T(\alpha)P_{j}\) is the most striking in contrast to that of \(T_{j}(\alpha)\). It gives better convergence properties for Algorithm 2, as shown in Sections 6 and 7.