About successive Gauss-Seidelisations (Q1970087)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | About successive Gauss-Seidelisations |
scientific article |
Statements
About successive Gauss-Seidelisations (English)
0 references
27 June 2000
0 references
Let \(F_1, F_2, \dots, F_n: \{0,1\}^n \rightarrow \{0,1\}\) be the component maps of a selfmapping \({\mathcal F}\) of the combinatorial \(n\)-cube. Consider the map \({\mathcal T}\colon \mathcal F \mapsto {\mathcal G}={\mathcal T}(\mathcal F)\) defined by component maps \(G_1(x)=F_1(x),\) \(G_p(x)=F_p(G_1(x), \dots, G_{p-1}(x), x_p, \dots, x_n),\) \(p=2,\dots,n.\) Let \({\mathcal G}_0={\mathcal F},\) and \({\mathcal G}_{i+1}= {\mathcal T}({\mathcal G}_i).\) Whatever the initial map \({\mathcal G}_0={\mathcal F},\) one has for \(n=2\) that \({\mathcal G}_1={\mathcal G}_3\) (proof by hand) and for \(n=3\) that \({\mathcal G}_7={\mathcal G}_3\) (proof by simulating calculus in \(\mathbb{Z}/2\mathbb{Z}\) via Gröbner bases). However, examples show that for \(n=4\) the transform \({\mathcal T}\) need not define cycles of length \(2^k\) with \(k<n.\) For formal analogies with the homonymous concept in numerical linear algebra, the authors call \({\mathcal T}(\mathcal F)\) the Gauss-Seidel transform of \({\mathcal F}\) and refer for other aspects to \textit{F. Robert} [Discrete iterations (1986; Zbl 0639.39005)] and \textit{F. Robert} and \textit{J. F. Maitre} [Numer. Math 19, 303-325 (1972; Zbl 0237.65028)] and some preprints.
0 references
discrete iteration
0 references
Boolean matrices
0 references
discrete Gauss Seidel transform
0 references