Summation Chains of Sequences Part 3: Sequence Chains from Linear Functions
For the full paper, which includes proofs, click here.
Abstract
(Editor’s note:) This paper represents the third installment of a masters thesis by Jonathan Johnson. The first two can be found here and here. This paper continues the development of the theory of summation chains of sequences. Since summation chains are doubly infinite, it’s important to know how little information we actually need to define a chain. The linearity of the function rules that generates a summation chain helps to answer this question. The notion of uniquely completable is defined from the set of positions, and several important theorems are developed to determine when a set of positions is uniquely completeable.
Introduction
(Editor’s note:) In Part 2, Johnson notes that summation chains can be generated by the function rule T_{\Sigma}: M^{\infty} \to M^{\infty},
T_{\Sigma}(x_{1}, x_{2}, x_{3},\ldots) = (x_{1}, x_{1} + x_{2}, x_{1} + x_{2} + x_{3},\ldots).
where M^{\infty} is a \mathbb{Z}-Module. This is a formal way to define the operator that generates the partial sums of a given sequence. Johnson proves in this installment that this function rule is a linear operator. The linearity of these function operators assists in determining how little information we need to know about the chain to be able to uniquely define it.
Johnson introduces the notion of the set of positions, which becomes the smallest amount of information that can define a summation chain under certain conditions.
Chains Generated by Linear Functions
Since vector-valued chains are vector-valued functions, they inherit the scalar multiplication and addition operations defined for functions on vector spaces. The linearity of the summation chain function rule leads to many interesting and useful results. The first of these is the closure of the set of summation chains under linear operations. This result holds for any function rule that is a linear operator.
Lemma.
Let M be a an 1-dimensional vector space with scalar field F. The summation function rule T_{\Sigma} defined in Remark 3.1 of [6] is a linear operator on M^{\infty}.
Proposition.
Let T:V\to V be a function rule where V is a vector space with scalar field F.
\mathcal{C}_T is closed under scalar multiplication and addition if and only if T is a linear operator.
Corollary 1.
Let T:V\to V be a bijective linear operator on vector space V with scalar field F, then \mathcal{C}_T is a subspace of the space of all functions from \mathbb{Z} to V, V^{\mathbb{Z}}, \Phi_{\Sigma[M]} is an isomorphism, and \mathcal{C}_T\cong V.
Corollary 2.
Let M be a an 1-dimensional vector space with scalar field F. \mathcal{C}_{\Sigma[M]} is a vector space, and \Phi_{\Sigma[M]} is an isomorphism from M^{\infty} to \mathcal{C}_{\Sigma[M]}.
Sets of Positions and Completeability
Viewing the summation operator as a linear operator is useful for answering the question on how little information must be known to define a chain.
Definition. A set of positions, U, is a nonempty subset of \mathbb{Z}\times\mathbb{N}. Let N\in\mathbb{N}, U_N=\{(m,n)\in U:n\leq N\}
Definition. Let M be an 1-dimensional vector space with scalar field F. Let T:M^{\infty}\to M^{\infty} be a bijective linear operator. A set of positions, U, is (uniquely) completable for T if for every function d:U\to M there exists a (unique) T-chain, c, such that c(m,n)=d(m,n) for all (m,n)\in U.
To say that a set of positions U is uniquely compleatable for T is the same as saying that every T-chain can be defined by defining each of the positions in U.
Lemma
Let M be an 1-dimensional vector space with scalar field F. Let T:M^{\infty}\to M^{\infty} be a bijective linear operator. Let U be a set of positions, U is completable for T if and only if every nonempty subset of U is completable for T.
Lemma
Let M be an 1-dimensional vector space with scalar field F. Let T:M^{\infty}\to M^{\infty} be a bijective linear operator. Let U be a set of positions, and let V be a set of positions containing U. If U is uniquely completable for T and V is completable for T, then V is uniquely completable for T.
How much information is needed to define a summation chain? The summation function rule has the additional property that it can be represented by an infinite-dimensional lower-triangular matrix. The question of how much information is need to define a summation chain will be addressed by studying matrices of this form. First, an ordering of the elements of \mathbb{Z}\times\mathbb{N} is defined in order to create a consistent indexing of sets of positions.
Definition. Let (m_1,n_1) and (m_2,n_2) be in \mathbb{Z}\times\mathbb{N}, define (m_1,n_1)\leq(m_2,n_2) to be the dictionary ordering n_1<n_2 or both n_1=n_2 and m_1\leq m_2.
Remark. This definition defines a total order on \mathbb{Z}\times\mathbb{N}.[7]
Lemma
Let U be a set of positions such that |U_N| is finite for all natural numbers, N, then U is well-ordered by the ordering in the above definition.
For the remainder of this section, given a set of positions, U, the elements U are assumed to be indexed by the well-ordering induced by the above definition, and (m_i,n_i)=u_i for all u_i\in U. Given a vector space M, a linear function rule T:M^{\infty}\to M^{\infty}, and a set of positions U, a linear function on M^{\infty} can be defined that maps a sequence x\in M^{\infty} to that values of the positions in U for \Phi_T(x).
Definition. Let M be an 1-dimensional vector space with scalar field F. Let T:M^{\infty}\to M^{\infty} be a bijective linear operator with a lower-triangular matrix. Let U be a set of positions such that the cardinality of U_N is finite for all natural numbers, N. The completion function for T with U is defined as follows.S^T_U:M^{\infty}\to M^{|U|} where for all x\in M^{\infty},
S^T_U(x)=[(T^{m_i}(x))_{n_i}]^{|U|}_{i=1}The remaining results in this section show how to use completion functions to determine the completeability of sets of positions.
Proposition
Let M be an 1-dimensional vector space with scalar field F. Let T:M^{\infty}\to M^{\infty} be a bijective linear operator with a lower-triangular matrix. Let U be a set of positions such that the cardinality of U_N is finite for all natural numbers, N.
- U is completable for T if and only if S^T_U is surjective.
- U is uniquely completable for T if and only if S^T_U is bijective.
Solving completion problems utilizes many properties of infinite matrices that can be referenced in Cooke [4]. The next proposition addresses sets of positions for which a completion function is not defined.
Proposition
Let M be an 1-dimensional vector space with scalar field F. Let U be a set of positions such that for a natural number, N, N<|U_N|, then U is not completable for any bijective linear operator T:M^{\infty}\to M^{\infty} with a lower-triangular matrix.
Proposition
Let M be an 1-dimensional vector space with scalar field F. Let U be a set of positions such that for a natural number, N, N = |U_N|, then U is uniquely completable for any bijective linear operator T:M^{\infty}\to M^{\infty} with a lower-triangular matrix.
Examples of Determining Completeability
Remark. Let S, T be linear transformations from vector space V to vector space W, and let P:W\to W be a bijective linear operator such that S=PV.
\dim\text{Im}(S)=\dim\text{Im}(T)
and S is bijective if and only if T is bijective.[4, 8]
Example 1.
\begin{array}{c|cccccccc}m\backslash n& 1 & 2 & 3 & 4 & 5 & 6 & 7 & \cdots\\\vdots & & & & & & &\\2& & & & & & &\\1 & & & \bigcirc & & \bigcirc & & \bigcirc\\0& & & \bigcirc & & \bigcirc & & \bigcirc\\-1& & & & & & &\\\vdots & & & & & & &\end{array}
Let T:\mathbb{R}^{\infty}\to\mathbb{R}^{\infty} where for (x_n)\in\mathbb{R}^{\infty}, T(x_n)=(y_n) defined as follows:
y_n= \left\{\begin{array}{ll}x_1& \text{ if } n=1\\x_3-x_1&\text{ if } n=3\\x_n&\text{ if } n\text{ is even}\\x_n-x_{n-3}&\text{ if } n>4 \text{ and } n \text{ is odd}\\\end{array}\right.
Let U=\{(0,n),(1,n):n\in\mathbb{N}, n>2, n \text{ is odd }\}.
\mathcal{M}(S^T_U)=\left( \begin{array}{cccccccc}0 & 0 & 1 & 0 & 0 & 0 & 0 & \cdots\\1 & 0 & 1 & 0 & 0 & 0 & 0 & \cdots\\0 & 0 & 0 & 0 & 1 & 0 & 0 & \cdots\\0 & 1 & 0 & 0 & 1 & 0 & 0 & \cdots\\0 & 0 & 0 & 0 & 0 & 0 & 1 & \cdots\\0 & 0 & 0 & 1 & 0 & 0 & 1 & \cdots\\\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots\end{array}\right)
Let A be the matrix row-equivalent to \mathcal{M}(S^T_U) defined as follows.
\begin{aligned}A&=\left( \begin{array}{ccccccccc}-1 & 1 & 0 & 0 & 0 & 0 & 0 & \cdots\\0 & 0 & 0& -1 & 1 & 0 & 0 & \cdots \\1 & 0 & 0 & 0 & 0 & 0 & 0 & \cdots\\0 & 0 & 0 & 0 & 0 & -1 & 1 & \cdots \\0 & 0 & 1 & 0 & 0 & 0 & 0 & \cdots\\\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots\end{array}\right)\left( \begin{array}{cccccccc}0 & 0 & 1 & 0 & 0 & 0 & 0 & \cdots\\1 & 0 & 1 & 0 & 0 & 0 & 0 & \cdots\\0 & 0 & 0 & 0 & 1 & 0 & 0 & \cdots\\0 & 1 & 0 & 0 & 1 & 0 & 0 & \cdots\\0 & 0 & 0 & 0 & 0 & 0 & 1 & \cdots\\0 & 0 & 0 & 1 & 0 & 0 & 1 & \cdots\\\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \end{array}\right)\\&=Id\\&=\left( \begin{array}{cccccccc}0 & 0 & 1 & 0 & 0 & 0 & 0 & \cdots\\1 & 0 & 1 & 0 & 0 & 0 & 0 & \cdots\\0 & 0 & 0 & 0 & 1 & 0 & 0 & \cdots\\0 & 1 & 0 & 0 & 1 & 0 & 0 & \cdots\\0 & 0 & 0 & 0 & 0 & 0 & 1 & \cdots\\0 & 0 & 0 & 1 & 0 & 0 & 1 & \cdots\\\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots\end{array}\right)\left( \begin{array}{ccccccccc}-1 & 1 & 0 & 0 & 0 & 0 & 0 & \cdots\\0 & 0 & 0 & -1 & 1 & 0 & 0 & \cdots \\1 & 0 & 0 & 0 & 0 & 0 & 0 & \cdots\\0 & 0 & 0 & 0 & 0 & -1 & 1 & \cdots \\0 & 0 & 1 & 0 & 0 & 0 & 0 & \cdots\\\vdots & \vdots & \vdots & \vdots & \vdots & \vdots &\vdots\end{array}\right)\\\end{aligned}
S^T_U has an inverse so S^T_U is bijective.Therefore, it is uniquely completable for T.
Example 2.
\begin{array}{c|cccccccc}m\backslash n& 1 & 2 & 3 & 4 & 5 & 6 & 7 & \cdots\\\vdots & & & & & & &\\2& & & & & & &\\1 & & \bigcirc &\bigcirc & & & & & \\0 & & & & \bigcirc & & & &\\-1& & & & \bigcirc & & & &\\2& & & & & & &\\\vdots & & & & & & &\end{array}
Let T be the summation operator on \mathbb{R}^{\infty} with a set of positions U=\{(1,2),(1,3),(-1,4),(0,4)\}.
\mathcal{M}(S^T_U)=\left(\begin{array}{cccccccc}1 & 1 & 0 & 0 & 0 & 0 & \cdots\\1 & 1 & 1 & 0 & 0 & 0 & \cdots\\0 & 0 & -1 & 1 & 0 & 0 & \cdots\\0 & 0 & 0 & 1 & 0 & 0 & \cdots\end{array}\right)Let A be the matrix row-equivalent to \mathcal{M}(S^T_U) defined as follows.
\begin{aligned}A&=\left(\begin{array}{cccc}1 & 0 & 0 & 0 \\-1 & 1 & 1 & -1 \\0 & 0 & -1 & 1 \\0 & 0 & 0 & 1 \end{array}\right)\left(\begin{array}{cccccccc}1 & 1 & 0 & 0 & 0 & 0 & \cdots\\1 & 1 & 1 & 0 & 0 & 0 & \cdots\\0 & 0 & -1 & 1 & 0 & 0 & \cdots\\0 & 0 & 0 & 1 & 0 & 0 & \cdots\end{array}\right)\\&=\left(\begin{array}{cccccccc}1 & 1 & 0 & 0 & 0 & 0 & \cdots\\0 & 0 & 0 & 0 & 0 & 0 & \cdots\\0 & 0 & 1 & 0 & 0 & 0 & \cdots\\0 & 0 & 0 & 1 & 0 & 0 & \cdots\end{array}\right)\end{aligned} \dim\text{Im}(S^T_U)=\text{rank}(A)=3<4 so S^T_U is not surjective. Therefore, U is not completable for T.
Example 3.
\begin{array}{c|cccccccc}m\backslash n& 1 & 2 & 3 & 4 & 5 & 6 & 7 & \cdots\\\vdots & & & & & & &\\4& & & & & & & &\\3& & & & & &\bigcirc & &\\2 & & & & \bigcirc & & & &\\1 & & \bigcirc & & & & & & \\0&&&&&& & &\\-1 & & \bigcirc & & & & & &\\-2 & & & & \bigcirc & & & &\\-3& & & & & &\bigcirc & &\\-4& & & & & & & &\\\vdots & & & & & & &\end{array}
Let T be the summation operator on \mathbb{R}^{\infty} with a set of positions U=\{(n,2n),(-n,2n):n\in\mathbb{N}\}.
\mathcal{M}(S^T_U)=\left(\begin{array}{ccccccccccc}1 & 1 & 0 & 0 & 0 & 0 & 0 & \cdots & 0 & 0 & \cdots\\-1 & 1 & 0 & 0 & 0 & 0 & 0 & \cdots & 0 & 0 & \cdots\\4 & 3 & 2 & 1 & 0 & 0 & 0 &\cdots & 0 & 0 & \cdots\\0 & 2 & -2 & 1 & 0 & 0 & 0 & \cdots & 0 & 0 & \cdots\\21 & 15 & 10 & 6 & 3 & 1 & 0 & \cdots & 0 & 0 & \cdots\\0 & 0 & -1 & 3 & -3 & 1 & 0 & \cdots & 0 & 0 & \cdots\\\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & & \vdots & \vdots & \\& & & & & & & \cdots & n & 1 & \cdots\\& & & & & & & \cdots & -n & 1 & \cdots\\& & & & & & & & \vdots & \vdots &\end{array}\right)\begin{array}{l}\\\\\\\\\\\\\\\leftarrow \text{ row } 2n-1\\\leftarrow\text{ row }2n\\\\\end{array}Let A be the matrix row-equivalent to \mathcal{M}(S^T_U) defined as follows.
\begin{aligned}A&=\left(\begin{array}{cccccccc}1 & -1 & 0 & 0 & 0 & 0 & \cdots\\0 & 1 & 0 & 0 & 0 & 0 & \cdots\\0 & 0 & 1 & -1 & 0 & 0 & \cdots\\0 & 0 & 0 & 1 & 0 & 0 & \cdots\\0 & 0 & 0 & 0 & 1 & -1 & \cdots\\0 & 0 & 0 & 0 & 0 & 1 & \cdots\\\vdots & \vdots & \vdots & \vdots & \vdots & \vdots\end{array}\right)\mathcal{M}(S^T_U)\\&=\left( \begin{array}{ccccccccccc}2 & 0 & 0 & 0 & 0 & 0 & 0 & \cdots & 0 & 0 & \cdots\\-1 & 1 & 0 & 0 & 0 & 0 & 0 & \cdots & 0 & 0 & \cdots\\4 & 1 & 4 & 0 & 0 & 0 & 0 &\cdots & 0 & 0 & \cdots\\0 & 2 & -2 & 1 & 0 & 0 & 0 & \cdots & 0 & 0 & \cdots\\21 & 15 & 11 & 3 & 6 & 0 & 0 & \cdots & 0 & 0 & \cdots\\0 & 0 & -1 & 3 & -3 & 1 & 0 & \cdots & 0 & 0 & \cdots\\\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & & \vdots & \vdots & \\& & & & & & & \cdots & 2n & 0 & \cdots\\& & & & & & & \cdots & -n & 1 & \cdots\\& & & & & & & & \vdots & \vdots & \end{array}\right)\\\end{aligned}Since A is lower-triangular with no zeros on the diagonal, A is the matrix of a bijective linear operator. Since A is equivalent to \mathcal{M}(S^T_U), S^T_U is bijective.
Therefore, U is uniquely completable for T.
Conclusion
(Editor’s Note): This installment examined sequence chains from linear functions with the goal of looking for the minimum amount of information necessary to uniquely define a summation chain. The set of positions was defined, and the notion of uniquely completable is based on this definition. Several elegant theorems gave the conditions under which the set of positions is uniquely completable. The fourth and final installment will discuss the notion of convergence for complex-valued summation chains.
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
References
- Apostol, T., 1974, Mathematical Analysis 2nd Edition, Addison-Wesley Publishing Company
- Brin, M. and Stuck, G., 2002, Introduction to Dynamical Systems, Cambridge University Press
- Cameron, P. J., 1992, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press
- Cook, R. G., 2014, Infinite Matrices and Sequence Spaces, Dover Publications, Inc.
- Johnson, J. (2017) Summation Chains of Sequences Part 1: Introduction, Generation, and Key Definitions. AACTO, Vol. 2, Issue 2.
- Johnson, J. (2017) Summation Chains of Sequences Part 2: Relationships Between Sequences via Summation Chains AACTO, Vol. 2, Issue 2.
- Lee, J., 2011, Introduction to Topological Manifolds, Springer Science+Business Media LLC
- Leon, S. J., 2002, Linear Algebra with Applications 6th Edition, Prentice Hall, Inc.
- Scheinerman, E. R., 1996, Invitation to Dynamical Systems, Dover Publications, Inc.