# Necessary and Sufficient Conditions for
Difference Flatness

Bernd Kolar<EMAIL_ADDRESS>Johannes Diwold<EMAIL_ADDRESS>Markus
Schöberl<EMAIL_ADDRESS>Institute of Automatic Control and Control
Systems Technology, Johannes Kepler University, Linz, Austria

###### Abstract

We show that the flatness of a nonlinear discrete-time system can be checked
by computing a unique sequence of involutive distributions. The well-known
test for static feedback linearizability is included as a special case. Since
the computation of the sequence of distributions requires only the solution of
algebraic equations, it allows an efficient implementation in a computer
algebra program. In case of a positive result, a flat output can be obtained
by straightening out the involutive distributions with the Frobenius theorem.
The resulting coordinate transformation can be used to transform the system
into a structurally flat implicit triangular form. We illustrate our results
by an example.

###### keywords:

Differential-geometric methods; Discrete-time systems; Nonlinear control
systems; Feedback linearization; Difference flatness; Normal forms.

, ,

##  1 Introduction

The concept of flatness has been introduced by Fliess, Lévine, Martin and
Rouchon in the 1990s for nonlinear continuous-time systems (see e.g. [4], [5],
and [6]). Flat continuous-time systems have the characteristic feature that
all system variables can be expressed by a flat output and its time
derivatives. The reason for their popularity lies in the fact that the
knowledge of a flat output allows an elegant solution to motion planning
problems, and a systematic design of tracking controllers. However, even
though the problem has attracted a lot of attention, there still exist no
efficiently verifiable necessary and sufficient conditions to check whether a
continuous-time system is flat or not. As a consequence, the construction of
flat outputs is a challenging problem, and represents the main obstacle in the
application of flatness-based methods.

For nonlinear discrete-time systems, flatness can be defined analogously to
the continuous-time case. The main difference is that time derivatives have to
be replaced by forward-shifts. To distinguish both concepts, often the terms
differential flatness and difference flatness are used (see e.g. [22]). Like
in the continuous-time case, flatness is closely related to the dynamic
feedback linearization problem, which is studied for discrete-time systems
e.g. in [1] and [2]. Flat discrete-time systems also form an extension of the
class of static feedback linearizable systems, and can be linearized by an
endogenous dynamic feedback (see e.g. [11]). The static feedback linearization
problem for discrete-time systems is already solved, see [7], [9], and [1].
The approach of [7] is similar to the well-known approach of [10] and [23] for
continuous-time systems, and allows to check whether a discrete-time system is
static feedback linearizable or not by computing a certain sequence of
involutive distributions. Subsequently, a linearizing output can be obtained,
roughly speaking, by straightening out these distributions with the Frobenius
theorem. Thus, the test for static feedback linearizability can be performed
independently from the calculation of a linearizing output. This separation is
very advantageous, since the computation of the distributions requires only
the solution of algebraic equations. The actual calculation of a linearizing
output by an application of the Frobenius theorem, in contrast, requires the
calculation of flows of vector fields, and therefore the solution of ODEs.

For checking the flatness of nonlinear discrete-time systems, until now no
comparable, computationally similarly efficient test is available. In [14], we
have shown that every flat system can be decomposed by coordinate
transformations into a subsystem and an endogenous dynamic feedback. The
advantage of such a decomposed form is that the complete system is flat if and
only if the subsystem is flat. A repeated application of this decomposition
allows to check whether a system with an $n$-dimensional state space is flat
or not in at most $n-1$ steps. However, the coordinate transformations that
achieve the decompositions are obtained by straightening out vector fields or
distributions with the flow-box theorem or the Frobenius theorem, which
requires the solution of ODEs. Therefore, the aim of the present paper is to
develop a test which only checks whether the decompositions are possible or
not, without actually performing them. This leads to a generalization of the
sequence of distributions from the static feedback linearization test of [7].
The proposed sequence of distributions is unique, and allows an efficient
computation. The dimension of the last distribution gives rise to necessary
and sufficient conditions for flatness. If the test yields a positive result,
then a flat output can be obtained, roughly speaking, by straightening the
distributions out. Furthermore, we show that the resulting coordinate
transformation transforms the system into a structurally flat implicit
triangular form. Thus, the main contribution of the paper is twofold. Firstly,
we present a novel test for flatness, which is a straightforward
generalization of the well-known test for static feedback linearizability.
Secondly, we show that every flat system can be transformed into a
structurally flat (implicit) normal form.

The paper is organized as follows: In Section 2 we recapitulate the concept of
flatness for discrete-time systems. Section 3 is devoted to mathematical
preliminaries, which are the foundation for the further investigations. In
Section 4 we introduce a sequence of distributions which generalizes the
sequence of distributions from the static feedback linearization test, and
show that it gives rise to necessary and sufficient conditions for flatness.
In Section 5, we show that straightening the distributions out yields a
coordinate transformation which transforms the system into a structurally flat
implicit triangular form. Finally, in Section 6 we illustrate our results by
an example.

##  2 Discrete-Time Systems and Flatness

In this contribution we consider discrete-time systems

$x^{i,+}=f^{i}(x,u)\,,\quad i=1,\ldots,n$ (1)

in state representation with $\dim(x)=n$, $\dim(u)=m$, and smooth functions
$f^{i}(x,u)$ that satisfy the submersivity condition

$\mathrm{rank}(\partial_{(x,u)}f)=n\,.$ (2)

Since the condition (2) is necessary for accessibility (see e.g. [8]) and
consequently also for flatness, it is no restriction. Geometrically, the
system (1) can be interpreted as a map

$f:\mathcal{X}\times\mathcal{U}\rightarrow\mathcal{X}\text{\textsuperscript{+}}$
(3)

from a manifold $\mathcal{X}\times\mathcal{U}$ with coordinates $(x,u)$ to a
manifold $\mathcal{X}\text{\textsuperscript{+}}$ with coordinates $x^{+}$. The
condition (2) ensures that this map is a submersion and therefore locally
surjective. The notation with a superscript $+$ is used to denote the forward-
shift of the corresponding variable. For the inputs and flat outputs we also
need higher forward-shifts, and use a subscript in brackets. For instance,
$u_{[\alpha]}$ denotes the $\alpha$-th forward-shift of $u$. To keep formulas
short and readable, we also use the Einstein summation convention.
Furthermore, it is important to emphasize that all our results are local. This
is due to the use of the inverse- and the implicit function theorem, the flow-
box theorem, and the Frobenius theorem, which allow only local results. A
fundamental difference to continuous-time systems is that for discrete-time
systems even in one time step the state can move far away from the initial
state, regardless of the input values. For continuous-time systems such a
problem does not appear, since by considering a sufficiently small time
interval it can always be ensured that the solution stays arbitrarily close to
the initial state. Therefore, in order not to loose localness, we work around
an equilibrium point

$x_{0}^{i}=f^{i}(x_{0},u_{0})\,,\quad i=1,\ldots,n$ (4)

of the system (1), see also [16] and [12]. To avoid mathematical subtleties,
we also assume that all functions are smooth.

In the following, we summarize the concept of difference flatness, see also
[14]. For this purpose, we introduce a space with coordinates
$(x,u,u_{[1]},u_{[2]},\ldots)$ and the forward-shift operator $\delta_{xu}$,
which acts on a function $g$ according to the rule

$\delta_{xu}(g(x,u,u_{[1]},u_{[2]},\ldots))=g(f(x,u),u_{[1]},u_{[2]},u_{[3]},\ldots)\,.$

A repeated application of $\delta_{xu}$ is denoted by $\delta_{xu}^{\alpha}$.
In this framework, an equilibrium (4) corresponds to a point
$(x_{0},u_{0},u_{0},u_{0},\ldots)$, and flatness of discrete-time systems can
be defined as follows.

######  Definition 1.

The system (1) is said to be flat around an equilibrium $(x_{0},u_{0})$, if
the $n+m$ coordinate functions $x$ and $u$ can be expressed locally by an
$m$-tuple of functions

$y^{j}=\varphi^{j}(x,u,u_{[1]},\ldots,u_{[q]})\,,\quad j=1,\ldots,m$ (5)

and their forward-shifts

$\begin{array}[]{ccl}y_{[1]}&=&\delta_{xu}(\varphi(x,u,u_{[1]},\ldots,u_{[q]}))\\\
y_{[2]}&=&\delta_{xu}^{2}(\varphi(x,u,u_{[1]},\ldots,u_{[q]}))\\\
&\vdots\end{array}$

up to some finite order. The $m$-tuple (5) is called a flat output.

The representation of $x$ and $u$ by the flat output and its forward-shifts is
unique, and has the form

$\begin{array}[]{cclcl}x^{i}&=&F_{x}^{i}(y_{[0,R-1]})\,,&&i=1,\ldots,n\\\
u^{j}&=&F_{u}^{j}(y_{[0,R]})\,,&&j=1,\ldots,m\,.\end{array}$ (6)

The multi-index $R=(r_{1},\ldots,r_{m})$ contains the number of forward-shifts
of each component of the flat output which is needed to express $x$ and $u$,
and $y_{[0,R]}$ is an abbreviation for $y$ and its forward-shifts up to order
$R$. Written in components,

$y_{[0,R]}=(y_{[0,r_{1}]}^{1},\ldots,y_{[0,r_{m}]}^{m})$

with

$y_{[0,r_{j}]}^{j}=(y^{j},y_{[1]}^{j},\ldots,y_{[r_{j}]}^{j})\,,\quad
j=1,\ldots,m\,.$

It is well-known that the map $(x,u)=F(y_{[0,R]})$ given by (6) is a
submersion, i.e., that the rows of its Jacobian matrix are linearly
independent, and that the highest forward-shifts
$y_{[R]}=(y_{[r_{1}]}^{1},\ldots,y_{[r_{m}]}^{m})$ only appear in the
parametrization $F_{u}$ of the input. If we substitute the parametrization (6)
into the identity

$\delta_{xu}(x^{i})=f^{i}(x,u)\,,\quad i=1,\ldots,n\,,$

we get the important identity

$\delta_{y}(F_{x}^{i}(y_{[0,R-1]}))=f^{i}\circ F(y_{[0,R]})\,,\quad
i=1,\ldots,n\,.$ (7)

Here $\delta_{y}$ is the forward-shift operator in coordinates
$(y,y_{[1]},y_{[2]},\ldots)$, which acts on a function $h$ according to the
rule

$\delta_{y}(h(y,y_{[1]},y_{[2]},\ldots))=h(y_{[1]},y_{[2]},y_{[3]},\ldots)\,.$

A fundamental consequence of the identity (7) is that the system equations (1)
do not impose any restrictions on the feasible trajectories

$y^{j}(k)\,,\quad j=1,\ldots,m$ (8)

of the flat output (5). For every trajectory (8) of the flat output, there
exists a uniquely determined solution $(x(k),u(k))$ of the system (1) such
that the equations

$y^{j}(k)=\varphi^{j}(x(k),u(k),u(k+1),\ldots,u(k+q))\,,$

$j=1,\ldots,m$ are satisfied identically. The corresponding trajectories
$x(k)$ and $u(k)$ of state and input are determined by $y(k)$ and its forward-
shifts via the parametrization (6). Thus, like in the case of differentially
flat continuous-time systems, there is a one-to-one correspondence between
solutions of the system (1) and arbitrary trajectories (8) of the flat output.

In Definition 1, we have made no assumption concerning the rank of the
Jacobian matrix $\partial_{u}f$. For a system (1) with
$\mathrm{rank}(\partial_{u}f)=\hat{m}<m$, there always exists an input
transformation $(\hat{u},\tilde{u})=\Phi_{u}(x,u)$ with
$\dim(\hat{u})=\hat{m}$ that eliminates $m-\hat{m}$ redundant inputs
$\tilde{u}$. There is a simple connection between a flat output of the
transformed system with $\hat{m}$ inputs, and the original system (1) with $m$
inputs.

######  Lemma 2.

Consider a system (1) with $\mathrm{rank}(\partial_{u}f)=\hat{m}<m$, and an
input transformation $(\hat{u},\tilde{u})=\Phi_{u}(x,u)$ with
$\dim(\hat{u})=\hat{m}$ that eliminates $m-\hat{m}$ redundant inputs
$\tilde{u}$. If an $\hat{m}$-tuple $\hat{y}$ is a flat output of the
transformed system

$x^{i,+}=\hat{f}^{i}(x,\hat{u})\,,\quad i=1,\ldots,n$ (9)

with the $\hat{m}$ inputs $\hat{u}$, then the $m$-tuple
$y=(\hat{y},\tilde{u})$ is a flat output of the original system (1) with the
$m$ inputs $u$.

######  Proof 2.1.

Since $\hat{y}$ is a flat output of the transformed system (9), $x$ and
$\hat{u}$ can be expressed as functions of $\hat{y}$ and its forward-shifts.
The inverse input transformation $u=\hat{\Phi}_{u}(x,\hat{u},\tilde{u})$ shows
immediately that the input $u$ of the original system (1) can be expressed by
$y=(\hat{y},\tilde{u})$ and its forward-shifts.

Thus, redundant inputs are candidates for components of a flat output. For the
proof of our main result, the necessary and sufficient conditions of Theorem 9
in Section 4, we also make use of a certain decomposed form, where the
complete system is flat if and only if a subsystem is flat.

######  Lemma 3.

A system of the form

$\begin{array}[]{lcl}x_{1}^{i_{1},+}=f_{1}^{i_{1}}(x_{1},x_{2},u_{1})\,,&&i_{1}=1,\ldots,n-m_{2}\\\
x_{2}^{i_{2},+}=f_{2}^{i_{2}}(x_{1},x_{2},u_{1},u_{2})\,,&&i_{2}=1,\ldots,m_{2}\end{array}$
(10)

with $\dim(u_{2})=\dim(x_{2})=m_{2}$ and
$\mathrm{rank}(\partial_{u}f)=\dim(u)=m$ is flat if and only if the subsystem

$x_{1}^{+}=f_{1}(x_{1},x_{2},u_{1})$ (11)

with the $m$ inputs $(x_{2},u_{1})$ is flat.

The proof is included in the appendix, and can also be found in [13] and [14].
The equations

$x_{2}^{i_{2},+}=f_{2}^{i_{2}}(x_{1},x_{2},u_{1},u_{2})\,,\quad
i_{2}=1,\ldots,m_{2}$

of (10) can be interpreted as an endogenous dynamic feedback for the subsystem
(11). This is in accordance with the fact that applying or removing an
endogenous dynamic feedback has no effect on the flatness of a system.

##  3 Projectable Vector Fields and Distributions

The necessary and sufficient conditions for flatness that we derive in Section
4 are formulated in terms of projectable distributions, which are closely
related to the notion of $f$-related vector fields. In the following we
summarize the basics of this concept, see also [14]. Further details can be
found in [3].

Let
$f_{*}:\mathcal{T}(\mathcal{X}\times\mathcal{U})\rightarrow\mathcal{T}(\mathcal{X}^{+})$
denote the tangent map of (3), and
$f_{*p}:\mathcal{T}_{p}(\mathcal{X}\times\mathcal{U})\rightarrow\mathcal{T}_{f(p)}(\mathcal{X}^{+})$
the tangent map of $f$ at some point $p\in\mathcal{X}\times\mathcal{U}$. If

$v=v_{x}^{i}(x,u)\partial_{x^{i}}+v_{u}^{j}(x,u)\partial_{u^{j}}$ (12)

is a vector field on $\mathcal{X}\times\mathcal{U}$, then the vector
$f_{*p}(v_{p})$ at $f(p)\in\mathcal{X}^{+}$ is called the pushforward of the
vector $v_{p}$ at $p\in\mathcal{X}\times\mathcal{U}$ by $f$. However, these
pointwise pushforwards of the vector field (12) do not necessarily induce a
well-defined vector field on $\mathcal{X}^{+}$. Since $f$ is only a submersion
and not a diffeomorphism, the inverse image $f^{-1}(q)$ of a point
$q\in\mathcal{X}^{+}$ is an $m$-dimensional submanifold of
$\mathcal{X}\times\mathcal{U}$, and it may happen that for a pair of points
$p_{1}$ and $p_{2}$ on this submanifold we get $f_{*p_{1}}(v_{p_{1}})\neq
f_{*p_{2}}(v_{p_{2}})$. In this case, the vector at the point
$f(p_{1})=f(p_{2})=q$ would not be unique. If, however, there exists a vector
field

$w=w^{i}(x^{+})\partial_{x^{i,+}}$ (13)

on $\mathcal{X}^{+}$ such that for all $q\in\mathcal{X}^{+}$ and $p\in
f^{-1}(q)\subset\mathcal{X}\times\mathcal{U}$ we have $f_{*p}(v_{p})=w_{q}$,
then the vector fields (12) and (13) are said to be $f$-related and we write
$w=f_{*}(v)$. For the components of the vector fields, $f$-relatedness means

$w^{i}(x^{+})\circ
f(x,u)=\partial_{x^{k}}f^{i}v_{x}^{k}(x,u)+\partial_{u^{j}}f^{i}v_{u}^{j}(x,u)\,,$
(14)

$i=1,\ldots,n$. Since $f$ is a submersion and therefore locally surjective,
the vector field (13) determined by a given vector field (12) is unique if it
exists. Moreover, as a submersion, the map $f$ induces a fibration (foliation)
of the manifold $\mathcal{X}\times\mathcal{U}$ with $m$-dimensional fibres
(leaves). Thus, we will adopt some terminology used for fibre bundles (see
e.g. [19]), and call vector fields (12) on $\mathcal{X}\times\mathcal{U}$ that
are $f$-related to a vector field (13) on $\mathcal{X}^{+}$ “projectable”.
Checking whether a vector field is projectable or not becomes very simple if
we use coordinates on $\mathcal{X}\times\mathcal{U}$ that are adapted to the
fibration. Adapted coordinates can be introduced by a transformation of the
form

$\begin{array}[]{ccl}\theta^{i}&=&f^{i}(x,u)\,,\quad i=1,\ldots,n\\\
\xi^{j}&=&h^{j}(x,u)\,,\quad j=1,\ldots,m\,,\end{array}$ (15)

where the $m$ functions $h^{j}(x,u)$ must be chosen such that the Jacobian
matrix

$\left[\begin{array}[]{cc}\partial_{x}f&\partial_{u}f\\\
\partial_{x}h&\partial_{u}h\end{array}\right]$

is regular. Because of the linear independence of the rows of the Jacobian
matrix of the submersion $f$, this is always possible and ensures that (15) is
a (local) diffeomorphism. With coordinates $(\theta,\xi)$ on
$\mathcal{X}\times\mathcal{U}$, the map (3) takes the simple form
$f=\mathrm{pr}_{1}$, i.e.,

$x^{i,+}=\theta^{i}\,,\quad i=1,\ldots,n\,.$ (16)

All points of $\mathcal{X}\times\mathcal{U}$ with the same value of $\theta$
belong to the same fibre and are mapped to the same point of
$\mathcal{X}^{+}$, regardless of the value of the fibre coordinates $\xi$. In
adapted coordinates, a vector field (12) on $\mathcal{X}\times\mathcal{U}$ has
in general the form

$v=a^{i}(\theta,\xi)\partial_{\theta^{i}}+b^{j}(\theta,\xi)\partial_{\xi^{j}}\,,$
(17)

and because of (16) an application of the tangent map $f_{*}$ yields

$f_{*}(v)=a^{i}(\theta,\xi)\partial_{x^{i,+}}\,.$ (18)

Obviously, the pointwise pushforward (18) of (17) induces a well-defined
vector field on $\mathcal{X}^{+}$ if and only if the functions $a^{i}$ are
independent of the coordinates $\xi$. In this case, replacing $\theta$ by
$x^{+}$ yields the vector field (13). In summary, a vector field (12) is
projectable if and only if in adapted coordinates (15) it has the form

$a^{i}(\theta)\partial_{\theta^{i}}+b^{j}(\theta,\xi)\partial_{\xi^{j}}\,,$
(19)

and the corresponding vector field (13) is given by

$a^{i}(x^{+})\partial_{x^{i,+}}\,.$

Similar to projectable vector fields, we will call a distribution $D$ on
$\mathcal{X}\times\mathcal{U}$ “projectable” if it admits a basis that
consists of projectable vector fields. The pushforward $f_{*}D$ of a
projectable distribution is a well-defined distribution on $\mathcal{X}^{+}$.
Since the Lie brackets $[v_{1},v_{2}]$ and $[w_{1},w_{2}]$ of two pairs
$v_{1},w_{1}$ and $v_{2},w_{2}$ of $f$-related vector fields are again
$f$-related, i.e.,

$f_{*}[v_{1},v_{2}]=[w_{1},w_{2}]\,,$

the pushforward of an involutive projectable distribution is again an
involutive distribution. The following theorem deals with the largest
projectable subdistribution of a given distribution on
$\mathcal{X}\times\mathcal{U}$, and is essential for our applications.

######  Theorem 4.

The largest projectable subdistribution $D_{P}\subset D$ of a distribution $D$
on $\mathcal{X}\times\mathcal{U}$ is uniquely determined. If $D$ is
involutive, then $D_{P}$ is also involutive.

######  Proof 3.1.

Introduce adapted coordinates (15) on $\mathcal{X}\times\mathcal{U}$, and
construct a new basis for $D$ which contains as many projectable vector fields
(19) as possible. These projectable vector fields are a basis for the largest
projectable subdistribution $D_{P}$. Every projectable vector field $v_{P}\in
D$ can be written as linear combination of these vector fields. If the
distribution $D$ is involutive, then all pairwise Lie brackets of the basis
vector fields of the projectable subdistribution $D_{P}\subset D$ must be
contained in $D$. However, since the basis vector fields of $D_{P}$ are
projectable, the Lie brackets are again projectable vector fields (see above).
Since by construction $D_{P}$ contains all projectable vector fields of $D$,
the subdistribution $D_{P}$ is involutive itself.

######  Remark 5.

It is important to note that not every vector field contained in a projectable
distribution is projectable itself. There only has to exist a basis that
consists of projectable vector fields. For instance, multiplying one of these
basis vector fields (with at least one component $a^{i}(\theta)\neq 0$) by a
function that depends on the fibre coordinates $\xi$ yields a non-projectable
vector field.

##  4 Necessary and Sufficient Conditions

In [14] it is shown that every flat discrete-time system satisfies the
following necessary condition, which can be interpreted as discrete-time
counterpart of the well-known ruled manifold necessary condition derived in
[18] for flat continuous-time systems.

######  Theorem 6.

The input distribution $\mathrm{span}\\{\partial_{u}\\}$ of a flat system (1)
with $\mathrm{rank}(\partial_{u}f)=m$ contains a nontrivial projectable vector
field.

In other words, the input distribution contains an at least 1-dimensional
projectable subdistribution. The proof is included in the appendix. Such a
projectable vector field or subdistribution can be used to transform the
system into the decomposed form (10) of Lemma 3, where the complete system is
flat if and only if the subsystem (11) is flat. Straightening out both the
vector field and its pushforward yields the required input- and state
transformations. As shown in [14], a repeated application of this
decomposition allows to check whether the system is flat or not in at most
$n-1$ steps. However, the coordinate transformations that achieve the
decompositions are constructed by straightening out vector fields with the
flow-box theorem, which requires the solution of ODEs. For this reason, in the
following we introduce a computationally more efficient test, which allows to
check whether the repeated decompositions are possible or not without actually
performing them. This test relies on sequences of nested distributions on
$\mathcal{X}\times\mathcal{U}$ and $\mathcal{X}\text{\textsuperscript{+}}$.
The construction of these sequences of distributions is based on the map (3)
defined by the system equations (1), and the map

$\pi:\mathcal{X}\times\mathcal{U}\rightarrow\mathcal{X}^{+}$

defined by

$x^{i,+}=x^{i}\,,\quad i=1,\ldots,n\,.$

We assume that locally the constructed distributions have constant dimension.
Algorithm 1 _._
_Step $0$:__Define the involutive distributions_

$\Delta_{0}=0$

_on $\mathcal{X}^{+}$ and_

$E_{0}=\pi_{*}^{-1}(\Delta_{0})=\mathrm{span}\\{\partial_{u}\\}$

_on $\mathcal{X}\times\mathcal{U}$. Then compute the largest subdistribution_

$D_{0}\subset E_{0}$

_which is projectable with respect to the map ( 3). Because of Theorem 4,
$D_{0}$ is unique and involutive. Thus, the pushforward_

$\Delta_{1}=f_{*}(D_{0})$

_is a well-defined involutive distribution on $\mathcal{X}^{+}$.___
_Step $k\geq 1$:__Define the involutive distribution_

$E_{k}=\pi_{*}^{-1}(\Delta_{k})$

_on $\mathcal{X}\times\mathcal{U}$. Because of
$\Delta_{k-1}\subset\Delta_{k}$, it satisfies $E_{k-1}\subset E_{k}$. Then
compute the largest subdistribution_

$D_{k}\subset E_{k}$ (20)

_which is projectable with respect to the map ( 3). Because of Theorem 4,
$D_{k}$ is unique and involutive. Moreover, because of $D_{k-1}\subset
E_{k-1}$ and $E_{k-1}\subset E_{k}$, it satisfies $D_{k-1}\subset D_{k}$.
Thus, the pushforward_

$\Delta_{k+1}=f_{*}(D_{k})$ (21)

_is a well-defined involutive distribution on $\mathcal{X}^{+}$ with_

$\Delta_{k}\subset\Delta_{k+1}\,.$ (22)

_Stop_ _if for some $k=\bar{k}$,_

$\dim(\Delta_{\bar{k}+1})=\dim(\Delta_{\bar{k}})\,.$

######  Remark 7.

It should be noted that the distributions $\Delta_{k}$ are indeed involutive,
since the pushforward of a projectable and involutive distribution $D_{k-1}$
is again an involutive distribution. Subsequently, the involutivity of
$\Delta_{k}$ implies the involutivity of $E_{k}$. For $k=0$ with
$E_{0}=\mathrm{span}\\{\partial_{u}\\}$, this is obvious. For $k\geq 1$ we
know that $\Delta_{k}$ is involutive, and can perform a state transformation
$(\tilde{x}_{1},\tilde{x}_{2})=\Phi_{x}(x)$ with
$\dim(\tilde{x}_{1})=\dim(\Delta_{k})$ such that
$\Delta_{k}=\mathrm{span}\\{\partial_{\tilde{x}_{1}^{+}}\\}$. In these
coordinates, $E_{k}=\mathrm{span}\\{\partial_{\tilde{x}_{1}},\partial_{u}\\}$
is straightened out, and therefore clearly involutive.

Because of (22) and $\dim(\mathcal{X}^{+})=n$, the procedure terminates after
at most $n$ steps. It yields a unique nested sequence of projectable and
involutive distributions

$D_{0}\subset D_{1}\subset\ldots\subset D_{\bar{k}-1}$ (23)

on $\mathcal{X}\times\mathcal{U}$, and a unique nested sequence of involutive
distributions

$\Delta_{1}\subset\Delta_{2}\subset\ldots\subset\Delta_{\bar{k}}$ (24)

on $\mathcal{X}^{+}$, which are related by the condition (21). Since we have
assumed that locally all these distributions have constant dimension, we can
define

$\rho_{k}=\dim(\Delta_{k})-\dim(\Delta_{k-1})\,,\quad k\geq 1$

with $\dim(\Delta_{0})=0$. Since the pushforward of linearly independent,
projectable vector fields on $\mathcal{X}\times\mathcal{U}$ does not
necessarily yield linearly independent vector fields on $\mathcal{X}^{+}$, it
is also important to note that in general

$\dim(\Delta_{k})\leq\dim(D_{k-1})\,.$

Therefore, we additionally define

$\mu_{k}=\dim(D_{k})-\dim(\Delta_{k+1})-\underbrace{\left(\dim(D_{k-1})-\dim(\Delta_{k})\right)}_{\mu_{0}+\ldots+\mu_{k-1}}\,,$
(25)

$k\geq 1$, which is just the number of linearly independent vector fields
$v\in D_{k}$ with $f_{*}(v)=0$ that are not contained in $D_{k-1}$. For $k=0$,
in the case $\mathrm{rank}(\partial_{u}f)=m$ we always have

$\mu_{0}=\dim(D_{0})-\dim(\Delta_{1})=0\,.$

The sequence (24) generalizes a sequence which was introduced in [7] to check
whether a discrete-time system (1) is static feedback linearizable or not.

######  Theorem 8.

A system (1) with $\mathrm{rank}(\partial_{u}f)=m$ is static feedback
linearizable if and only if $D_{k}=E_{k}$, $k\geq 0$ and
$\dim(\Delta_{\bar{k}})=n$.

In other words, in every step the complete distribution $E_{k}$ must be
projectable. For a proof, see [7] and [17]. If we drop the condition
$D_{k}=E_{k}$, we get necessary and sufficient conditions for flatness.

######  Theorem 9.

A system (1) with $\mathrm{rank}(\partial_{u}f)=m$ is flat if and only if
$\dim(\Delta_{\bar{k}})=n$.

Before we can prove Theorem 9, we have to establish some further properties of
the sequences (23) and (24). The basic idea of the proof, however, is to use
the distributions (23) and (24) for a stepwise decomposition of the system (1)
into subsystems and endogenous dynamic feedbacks exactly like in [14]. In the
case $\dim(\Delta_{\bar{k}})=n$, we can decompose the system until only the
trivial system is left, which proves that the system is flat. Otherwise, we
will encounter a subsystem which allows no further decomposition. However,
since a flat discrete-time system always allows a decomposition, in the latter
case the system cannot be flat.

First, it is important to note that the nested sequence of involutive
distributions (24) on $\mathcal{X}^{+}$ can be straightened out by a state
transformation

$(\bar{x}_{1},\ldots,\bar{x}_{\bar{k}},\bar{x}_{rest})=\Phi_{x}(x)$ (26)

with $\dim(\bar{x}_{k})=\rho_{k}$, $k=1,\ldots,\bar{k}$ such that

$\begin{array}[]{ccl}\Delta_{1}&=&\mathrm{span}\\{\partial_{\bar{x}_{1}^{+}}\\}\\\
\Delta_{2}&=&\mathrm{span}\\{\partial_{\bar{x}_{1}^{+}},\partial_{\bar{x}_{2}^{+}}\\}\\\
&\vdots\\\
\Delta_{\bar{k}}&=&\mathrm{span}\\{\partial_{\bar{x}_{1}^{+}},\partial_{\bar{x}_{2}^{+}},\ldots,\partial_{\bar{x}_{\bar{k}}^{+}}\\}\,.\end{array}$

The state transformation (26) is performed both for the variables $x$ and the
shifted variables $x^{+}$. Because of (21), the transformed system

$\begin{array}[]{ccl}\bar{x}_{rest}^{+}&=&f_{rest}(\bar{x},u)\\\
\bar{x}_{\bar{k}}^{+}&=&f_{\bar{k}}(\bar{x},u)\\\ &\vdots\\\
\bar{x}_{2}^{+}&=&f_{2}(\bar{x},u)\\\
\bar{x}_{1}^{+}&=&f_{1}(\bar{x},u)\end{array}$ (27)

meets

$\begin{array}[]{ccl}f_{*}(D_{0})&=&\mathrm{span}\\{\partial_{\bar{x}_{1}^{+}}\\}\\\
f_{*}(D_{1})&=&\mathrm{span}\\{\partial_{\bar{x}_{1}^{+}},\partial_{\bar{x}_{2}^{+}}\\}\\\
&\vdots\\\
f_{*}(D_{\bar{k}-1})&=&\mathrm{span}\\{\partial_{\bar{x}_{1}^{+}},\partial_{\bar{x}_{2}^{+}},\ldots,\partial_{\bar{x}_{\bar{k}}^{+}}\\}\,.\end{array}$
(28)

In these coordinates, the involutive distributions

$E_{k}=\pi_{*}^{-1}(\Delta_{k})=\mathrm{span}\\{\partial_{\bar{x}_{k}},\ldots,\partial_{\bar{x}_{1}},\partial_{u}\\}\,,$

$k=0,\ldots,\bar{k}-1$, are exactly the input distributions of the subsystems

$\begin{array}[]{ccl}\bar{x}_{rest}^{+}&=&f_{rest}(\bar{x}_{rest},\bar{x}_{\bar{k}},\ldots,\bar{x}_{1},u)\\\
\bar{x}_{\bar{k}}^{+}&=&f_{\bar{k}}(\bar{x}_{rest},\bar{x}_{\bar{k}},\ldots,\bar{x}_{1},u)\\\
&\vdots\\\
\bar{x}_{k+1}^{+}&=&f_{k+1}(\bar{x}_{rest},\bar{x}_{\bar{k}},\ldots,\bar{x}_{1},u)\end{array}$
(29)

of (27). Among the inputs $(\bar{x}_{k},\ldots,\bar{x}_{1},u)$ of these
subsystems there are of course redundant inputs.

######  Lemma 10.

The rank of the Jacobian matrix

$\left[\begin{array}[]{cccc}\partial_{\bar{x}_{k}}f_{rest}&\cdots&\partial_{\bar{x}_{1}}f_{rest}&\partial_{u}f_{rest}\\\
\partial_{\bar{x}_{k}}f_{\bar{k}}&\cdots&\partial_{\bar{x}_{1}}f_{\bar{k}}&\partial_{u}f_{\bar{k}}\\\
\vdots&&\vdots&\vdots\\\
\partial_{\bar{x}_{k}}f_{k+1}&\cdots&\partial_{\bar{x}_{1}}f_{k+1}&\partial_{u}f_{k+1}\end{array}\right]$
(30)

of the subsystem (29) with respect to its inputs
$(\bar{x}_{k},\ldots,\bar{x}_{1},u)$ is given by

$m-\left(\dim(D_{k})-\dim(\Delta_{k+1})\right)\,.$ (31)

######  Proof 4.1.

The Jacobian matrix (30) has

$\rho_{k}+\ldots+\rho_{1}+m=\dim(\Delta_{k})+m$

columns. To prove the lemma, we simply calculate the dimension of its kernel.
For the distribution $D_{k}\subset E_{k}$ with $f_{*}(D_{k})=\Delta_{k+1}$,
there exists a basis that contains $\dim(D_{k})-\rho_{k+1}$ vector fields with
a pushforward that lies in $\Delta_{k}\subset\Delta_{k+1}$. Written as column
vectors, these $\dim(D_{k})-\rho_{k+1}$ vector fields lie in the kernel of the
Jacobian matrix (30). Thus, the matrix has a kernel of dimension at least
$\dim(D_{k})-\rho_{k+1}$. However, every vector field $v\in E_{k}$ which lies
in the kernel of (30) has a pushforward that lies in $\Delta_{k}$, and because
of $f_{*}(D_{k-1})=\Delta_{k}$ it is certainly contained in $D_{k}$. Thus, the
dimension of the kernel is exactly $\dim(D_{k})-\rho_{k+1}$. Subtracting the
dimension of the kernel from the number of columns gives the rank

$\dim(\Delta_{k})+m-\left(\dim(D_{k})-\rho_{k+1}\right)\,.$

With $\rho_{k+1}=\dim(\Delta_{k+1})-\dim(\Delta_{k})$ the result (31) follows.

With the definition (25) of the integers $\mu_{k}$, the rank (31) of the
Jacobian matrix (30) is given by

$m-(\mu_{0}+\ldots+\mu_{k})\,.$

If the system (1) is static feedback linearizable, then, as shown in [7] and
[17], the state transformation (26) transforms the system into a triangular
form

$\begin{array}[]{ccl}\bar{x}_{\bar{k}}^{+}&=&f_{\bar{k}}(\bar{x}_{\bar{k}},\bar{x}_{\bar{k}-1})\\\
&\vdots\\\
\bar{x}_{2}^{+}&=&f_{2}(\bar{x}_{\bar{k}},\bar{x}_{\bar{k}-1},\ldots,\bar{x}_{1})\\\
\bar{x}_{1}^{+}&=&f_{1}(\bar{x}_{\bar{k}},\bar{x}_{\bar{k}-1},\ldots,\bar{x}_{1},u)\,.\end{array}$
(32)

The reason is that straightening out the sequence (24) simultaneously
straightens out the sequence $E_{0}\subset E_{1}\subset\ldots\subset
E_{\bar{k}-1}$. For static feedback linearizable systems we have
$D_{k}=E_{k}$, $k\geq 0$, and consequently

$D_{k}=\mathrm{span}\\{\partial_{\bar{x}_{k}},\ldots,\partial_{\bar{x}_{1}},\partial_{u}\\}\,,\quad
k=0,\ldots,\bar{k}-1\,.$

Evaluating the condition (28) shows that the transformed system (27) with
$\dim(\bar{x}_{rest})=0$ must have the triangular form (32). If the condition
$D_{k}=E_{k}$ does not hold for all $k=0,\ldots,\bar{k}-1$, then the state
transformation (26) that straightens out the sequence (24) does in general not
straighten out the sequence (23).

In the following, we prove Theorem 9. The proof is performed for the system
(27) after the state transformation (26).

###  4.1 Proof of Theorem 9

The idea of the proof is to straighten out the sequence (23) in $\bar{k}$
steps with coordinate transformations on $\mathcal{X}\times\mathcal{U}$ that
can be interpreted as input transformations for the subsystems (29),
$k=0,\ldots,\bar{k}-1$. These transformations lead to a sequence of decomposed
subsystems, and show inductively that the complete system (27) is flat if and
only if the subsystem with $f_{rest}$ is flat.

First, we decompose the system (27) by straightening out $D_{0}$. Because of

$D_{0}\subset E_{0}=\mathrm{span}\\{\partial_{u}\\}\,,$

there exists an input transformation

$(\eta_{0},\hat{z}_{0})=\Phi_{0}(\bar{x},u)$

with inverse $u=\hat{\Phi}_{0}(\bar{x},\eta_{0},\hat{z}_{0})$ such that

$D_{0}=\mathrm{span}\\{\partial_{\hat{z}_{0}}\\}\,.$

Because of $f_{*}(D_{0})=\mathrm{span}\\{\partial_{\bar{x}_{1}^{+}}\\}$, in
these coordinates the functions $f_{2},\ldots,f_{\bar{k}},f_{rest}$ are
independent of $\hat{z}_{0}$, i.e.,

$\begin{array}[]{ccl}\bar{x}_{rest}^{+}&=&f_{rest}(\bar{x}_{rest},\bar{x}_{\bar{k}},\ldots,\bar{x}_{2},\bar{x}_{1},\eta_{0})\\\
\bar{x}_{\bar{k}}^{+}&=&f_{\bar{k}}(\bar{x}_{rest},\bar{x}_{\bar{k}},\ldots,\bar{x}_{2},\bar{x}_{1},\eta_{0})\\\
&\vdots\\\
\bar{x}_{2}^{+}&=&f_{2}(\bar{x}_{rest},\bar{x}_{\bar{k}},\ldots,\bar{x}_{2},\bar{x}_{1},\eta_{0})\\\
\bar{x}_{1}^{+}&=&f_{1}(\bar{x}_{rest},\bar{x}_{\bar{k}},\ldots,\bar{x}_{2},\bar{x}_{1},\eta_{0},\hat{z}_{0})\,.\end{array}$

Since the system (27) does not have redundant inputs, the condition

$\mathrm{rank}(\partial_{\hat{z}_{0}}f_{1})=\dim(\hat{z}_{0})=\rho_{1}$

holds. Thus, the system is flat if and only if the subsystem
$f_{2},\ldots,f_{\bar{k}},f_{rest}$ with the inputs $(\bar{x}_{1},\eta_{0})$
is flat (cf. Lemma 3). Next, because of the rank condition (31), we can
eliminate $\mu_{1}$ redundant inputs $y_{1}$ of this subsystem by an input
transformation

$(\zeta_{1},y_{1})=\Psi_{1}(\bar{x}_{rest},\bar{x}_{\bar{k}},\ldots,\bar{x}_{2},\bar{x}_{1},\eta_{0})$

with inverse
$(\bar{x}_{1},\eta_{0})=\hat{\Psi}_{1}(\bar{x}_{rest},\bar{x}_{\bar{k}},\ldots,\bar{x}_{2},\zeta_{1},y_{1})$.
This yields

$\begin{array}[]{ccl}\bar{x}_{rest}^{+}&=&f_{rest}(\bar{x}_{rest},\bar{x}_{\bar{k}},\ldots,\bar{x}_{2},\zeta_{1})\\\
\bar{x}_{\bar{k}}^{+}&=&f_{\bar{k}}(\bar{x}_{rest},\bar{x}_{\bar{k}},\ldots,\bar{x}_{2},\zeta_{1})\\\
&\vdots\\\
\bar{x}_{2}^{+}&=&f_{2}(\bar{x}_{rest},\bar{x}_{\bar{k}},\ldots,\bar{x}_{2},\zeta_{1})\\\
\bar{x}_{1}^{+}&=&f_{1}(\bar{x}_{rest},\bar{x}_{\bar{k}},\ldots,\bar{x}_{2},\zeta_{1},y_{1},\hat{z}_{0})\end{array}$

with $\dim(\zeta_{1})=m-(\dim(D_{1})-\dim(\Delta_{2}))$ according to (31). Now
that all redundant inputs are eliminated, we decompose the subsystem
$f_{2},\ldots,f_{\bar{k}},f_{rest}$ by straightening out the distribution

$D_{1}\subset
E_{1}=\mathrm{span}\\{\partial_{\hat{z}_{0}},\partial_{y_{1}},\partial_{\zeta_{1}}\\}\,.$

Because of $D_{0}\subset D_{1}$ and
$f_{*}(\partial_{y_{1}})\subset\mathrm{span}\\{\partial_{\bar{x}_{1}^{+}}\\}$
we already have

$\mathrm{span}\\{\partial_{\hat{z}_{0}},\partial_{y_{1}}\\}\subset D_{1}\,,$

and consequently $D_{1}$ has a basis of the form

$\displaystyle\partial_{\hat{z}_{0}^{i_{0}}}\,,$ $\displaystyle\quad
i_{0}=1,\ldots,\rho_{1}$ $\displaystyle\partial_{y_{1}^{j_{1}}}\,,$
$\displaystyle\quad j_{1}=1,\ldots,\mu_{1}$
$\displaystyle\sum_{l=1}^{\dim(\zeta_{1})}v_{i_{1}}^{l}(\bar{x}_{rest},\ldots,\bar{x}_{2},\zeta_{1},y_{1},\hat{z}_{0})\partial_{\zeta_{1}^{l}}\,,$
$\displaystyle\quad i_{1}=1,\ldots,\rho_{2}\,.$

Up to a renumbering of the components of $\zeta_{1}$, there even exists a
basis

$\displaystyle\partial_{\hat{z}_{0}^{i_{0}}}\,,$ $\displaystyle\quad
i_{0}=1,\ldots,\rho_{1}$ $\displaystyle\partial_{y_{1}^{j_{1}}}\,,$
$\displaystyle\quad j_{1}=1,\ldots,\mu_{1}$
$\displaystyle\partial_{\zeta_{1}^{i_{1}}}+\sum_{l=\rho_{2}+1}^{\dim(\zeta_{1})}\hat{v}_{i_{1}}^{l}(\bar{x}_{rest},\ldots,\bar{x}_{2},\zeta_{1})\partial_{\zeta_{1}^{l}}\,,$
$\displaystyle\quad i_{1}=1,\ldots,\rho_{2}\,,$

which, written in matrix form, contains a block with an identity matrix. Thus,
the involutivity of $D_{1}$ implies that all pairwise Lie brackets of the
vector fields vanish. This in turn implies that the coefficients of the last
$\rho_{2}$ vector fields are independent of $\hat{z}_{0}$ and $y_{1}$.
Therefore, these vector fields can be straightened out by a transformation of
the form

$(\eta_{1},\hat{z}_{1})=\Phi_{1}(\bar{x}_{rest},\bar{x}_{\bar{k}},\ldots,\bar{x}_{2},\zeta_{1})$

with inverse
$\zeta_{1}=\hat{\Phi}_{1}(\bar{x}_{rest},\bar{x}_{\bar{k}},\ldots,\bar{x}_{2},\eta_{1},\hat{z}_{1})$,
which can be interpreted as an input transformation for the subsystem
$f_{2},\ldots,f_{\bar{k}},f_{rest}$. In new coordinates we have

$D_{1}=\mathrm{span}\\{\partial_{\hat{z}_{0}},\partial_{y_{1}},\partial_{\hat{z}_{1}}\\}\,,$

and because of
$f_{*}(D_{1})=\mathrm{span}\\{\partial_{\bar{x}_{1}^{+}},\partial_{\bar{x}_{2}^{+}}\\}$
the functions $f_{3},\ldots,f_{\bar{k}},f_{rest}$ are independent of
$\hat{z}_{0}$, $y_{1}$, and $\hat{z}_{1}$. Thus, we get

$\begin{array}[]{ccl}\bar{x}_{rest}^{+}&=&f_{rest}(\bar{x}_{rest},\bar{x}_{\bar{k}},\ldots,\bar{x}_{2},\eta_{1})\\\
\bar{x}_{\bar{k}}^{+}&=&f_{\bar{k}}(\bar{x}_{rest},\bar{x}_{\bar{k}},\ldots,\bar{x}_{2},\eta_{1})\\\
&\vdots\\\
\bar{x}_{3}^{+}&=&f_{3}(\bar{x}_{rest},\bar{x}_{\bar{k}},\ldots,\bar{x}_{2},\eta_{1})\\\
\bar{x}_{2}^{+}&=&f_{2}(\bar{x}_{rest},\bar{x}_{\bar{k}},\ldots,\bar{x}_{2},\eta_{1},\hat{z}_{1})\\\
\bar{x}_{1}^{+}&=&f_{1}(\bar{x}_{rest},\bar{x}_{\bar{k}},\ldots,\bar{x}_{2},\eta_{1},\hat{z}_{1},y_{1},\hat{z}_{0})\end{array}$

and

$\mathrm{rank}(\partial_{\hat{z}_{1}}f_{2})=\dim(\hat{z}_{1})=\rho_{2}\,.$

Consequently, the system is flat if and only if the subsystem
$f_{3},\ldots,f_{\bar{k}},f_{rest}$ with the inputs $(\bar{x}_{2},\eta_{1})$
is flat. In the following steps, we proceed analogously. First, we eliminate
all redundant inputs of the subsystem $f_{k+1},\ldots,f_{\bar{k}},f_{rest}$,
$k\geq 2$. Subsequently, we decompose the subsystem by straightening out the
distribution $D_{k}$ with a transformation that can be interpreted as an input
transformation for the subsystem. Continuing this procedure until
$k=\bar{k}-1$ transforms the system (27) into the form

$\begin{array}[]{ccl}\bar{x}_{rest}^{+}&=&f_{rest}(\bar{x}_{rest},\bar{x}_{\bar{k}},\eta_{\bar{k}-1})\\\
\bar{x}_{\bar{k}}^{+}&=&f_{\bar{k}}(\bar{x}_{rest},\bar{x}_{\bar{k}},\eta_{\bar{k}-1},\hat{z}_{\bar{k}-1})\\\
&\vdots\\\
\bar{x}_{2}^{+}&=&f_{2}(\bar{x}_{rest},\bar{x}_{\bar{k}},\eta_{\bar{k}-1},\hat{z}_{\bar{k}-1},y_{\bar{k}-1},\ldots,\hat{z}_{2},y_{2},\hat{z}_{1})\\\
\bar{x}_{1}^{+}&=&f_{1}(\bar{x}_{rest},\bar{x}_{\bar{k}},\eta_{\bar{k}-1},\hat{z}_{\bar{k}-1},y_{\bar{k}-1},\ldots,\hat{z}_{1},y_{1},\hat{z}_{0})\,,\end{array}$
(33)

and shows by a repeated application of Lemma 3 that the complete system is
flat if and only if the subsystem

$\begin{array}[]{ccc}\bar{x}_{rest}^{+}&=&f_{rest}(\bar{x}_{rest},\bar{x}_{\bar{k}},\eta_{\bar{k}-1})\end{array}$
(34)

with the inputs $(\bar{x}_{\bar{k}},\eta_{\bar{k}-1})$ is flat.

In the case $\dim(\Delta_{\bar{k}})=n$, because of $\dim(\bar{x}_{rest})=0$
the subsystem (34) is an empty system with inputs
$(\bar{x}_{\bar{k}},\eta_{\bar{k}-1})$. Therefore, the complete system is
flat, and

$y=(y_{\bar{k}},y_{\bar{k}-1},\ldots,y_{1})$ (35)

with $y_{\bar{k}}=(\bar{x}_{\bar{k}},\eta_{\bar{k}-1})$ is a flat output. The
flat output (35) consists of the inputs of the (empty) system (34), and the
redundant inputs $(y_{\bar{k}-1},\ldots,y_{1})$ of the subsystems that have
been eliminated during the repeated decompositions (cf. Lemma 2). The flat
output in original coordinates can be obtained by applying the inverse
coordinate transformations.

For the case $\dim(\Delta_{\bar{k}})<n$, we show by contradiction that the
subsystem (34) with $\dim(\bar{x}_{rest})>0$ cannot be flat. First, we
eliminate all redundant inputs by an input transformation

$(\zeta_{\bar{k}},y_{\bar{k}})=\Psi_{\bar{k}}(\bar{x}_{rest},\bar{x}_{\bar{k}},\eta_{\bar{k}-1})$

with inverse
$(\bar{x}_{\bar{k}},\eta_{\bar{k}-1})=\hat{\Psi}_{\bar{k}}(\bar{x}_{rest},\zeta_{\bar{k}},y_{\bar{k}})$.
If the resulting system

$\begin{array}[]{ccc}\bar{x}_{rest}^{+}&=&f_{rest}(\bar{x}_{rest},\zeta_{\bar{k}})\end{array}$
(36)

would be flat, then according to the necessary condition of Theorem 6 there
would exist a nontrivial vector field

$v^{l}(\bar{x}_{rest},\zeta_{\bar{k}})\partial_{\zeta_{\bar{k}}^{l}}$

which is projectable with respect to the subsystem (36). With respect to the
complete system, such a vector field would be contained in the largest
projectable subdistribution $D_{\bar{k}}\subset E_{\bar{k}}$, and accordingly
the dimension of $\Delta_{\bar{k}+1}=f_{*}(D_{\bar{k}})$ would be larger than
the dimension of $\Delta_{\bar{k}}=f_{*}(D_{\bar{k}-1})$. However, because of
$\dim(\Delta_{\bar{k}+1})=\dim(\Delta_{\bar{k}})$ such a vector field does not
exist.

##  5 Implicit Triangular Form

Every static feedback linearizable system can be transformed by a state
transformation (26) into the triangular form (32), and with a further
coordinate transformation the Brunovsky normal form can be obtained. For flat
systems that are not static feedback linearizable, a transformation into the
Brunovsky normal form is not possible (without a dynamic feedback). However,
in this section we prove that every flat discrete-time system can be
transformed into a structurally flat implicit triangular form, with variables
that are partitioned into blocks $z_{k}=(y_{k},\hat{z}_{k})$ according to

$\begin{array}[]{ccl}z&=&(z_{\bar{k}},z_{\bar{k}-1},\ldots,z_{1},z_{0})\\\
&=&(y_{\bar{k}},(y_{\bar{k}-1},\hat{z}_{\bar{k}-1}),\ldots,(y_{1},\hat{z}_{1}),\hat{z}_{0})\,,\end{array}$
(37)

and equations

$\begin{array}[]{cl}\Xi_{\bar{k}}:&w_{\bar{k}}(z_{\bar{k}}^{+},z_{\bar{k}},\hat{z}_{\bar{k}-1})=0\\\
\Xi_{\bar{k}-1}:&w_{\bar{k}-1}(z_{\bar{k}}^{+},z_{\bar{k}-1}^{+},z_{\bar{k}},z_{\bar{k}-1},\hat{z}_{\bar{k}-2})=0\\\
\vdots\\\
\Xi_{2}:&w_{2}(z_{\bar{k}}^{+},\ldots,z_{2}^{+},z_{\bar{k}},\ldots,z_{2},\hat{z}_{1})=0\\\
\Xi_{1}:&w_{1}(z_{\bar{k}}^{+},\ldots,z_{1}^{+},z_{\bar{k}},\ldots,z_{1},\hat{z}_{0})=0\end{array}$
(38)

with $\dim(\Xi_{k})=\dim(\hat{z}_{k-1})$, $k=1,\ldots,\bar{k}$ that satisfy
the rank conditions

$\mathrm{rank}(\partial_{\hat{z}_{k-1}}w_{k})=\dim(\hat{z}_{k-1})\,,\quad
k=1,\ldots,\bar{k}\,.$ (39)

The components $y_{k}$ with $k=1,\ldots,\bar{k}-1$ of (37) may be empty. The
triangular form (38) was introduced in [15], and is the discrete-time
counterpart to the implicit triangular form that is discussed in [21] and [20]
for flat continuous-time systems. It has the property that the variables
$y=(y_{\bar{k}},y_{\bar{k}-1},\ldots,y_{0})$ form a flat output, and because
of the rank conditions (39), the parametrization of the other system variables
$(\hat{z}_{\bar{k}-1},\ldots,\hat{z}_{0})$ can be obtained directly from the
equations (38) and the implicit function theorem. From the topmost block of
equations $\Xi_{\bar{k}}$ we get the parametrization of the variables
$\hat{z}_{\bar{k}-1}$, from the next block of equations $\Xi_{\bar{k}-1}$ we
get the parametrization of the variables $\hat{z}_{\bar{k}-2}$, and so on.

######  Theorem 11.

Every flat system (1) with $\mathrm{rank}(\partial_{u}f)=m$ can be transformed
into the structurally flat implicit triangular form (38).

######  Proof 5.1.

First, the system (1) is transformed into the form (27) by straightening out
the nested sequence of distributions (24) with a state transformation (26).
Since the system is flat, we have $\dim(\Delta_{\bar{k}})=n$ and
$\dim(\bar{x}_{rest})=0$. If we combine the coordinate transformations on
$\mathcal{X}\times\mathcal{U}$ that are constructed in the proof of Theorem 9,
we get a coordinate transformation of the form

$\begin{array}[]{ccl}\bar{x}_{\bar{k}}&=&\bar{x}_{\bar{k}}\\\
\bar{x}_{\bar{k}-1}&=&\Phi_{\bar{k}-1}(\bar{x}_{\bar{k}},\eta_{\bar{k}-1},\hat{z}_{\bar{k}-1},y_{\bar{k}-1})\\\
&\vdots\\\
\bar{x}_{2}&=&\Phi_{2}(\bar{x}_{\bar{k}},\eta_{\bar{k}-1},\hat{z}_{\bar{k}-1},y_{\bar{k}-1},\ldots,\hat{z}_{2},y_{2})\\\
\bar{x}_{1}&=&\Phi_{1}(\bar{x}_{\bar{k}},\eta_{\bar{k}-1},\hat{z}_{\bar{k}-1},y_{\bar{k}-1},\ldots,\hat{z}_{2},y_{2},\hat{z}_{1},y_{1})\\\
u&=&\Phi_{u}(\bar{x}_{\bar{k}},\eta_{\bar{k}-1},\hat{z}_{\bar{k}-1},y_{\bar{k}-1},\ldots,\hat{z}_{2},y_{2},\hat{z}_{1},y_{1},\hat{z}_{0})\,.\end{array}$
(40)

This coordinate transformation straightens out the sequence (23) according to

$\begin{array}[]{ccl}D_{0}&=&\mathrm{span}\\{\partial_{\hat{z}_{0}}\\}\\\
D_{1}&=&\mathrm{span}\\{\partial_{\hat{z}_{0}},\partial_{y_{1}},\partial_{\hat{z}_{1}}\\}\\\
&\vdots\\\
D_{\bar{k}-1}&=&\mathrm{span}\\{\partial_{\hat{z}_{0}},\partial_{y_{1}},\partial_{\hat{z}_{1}},\ldots,\partial_{y_{\bar{k}-1}},\partial_{\hat{z}_{\bar{k}-1}}\\}\,,\end{array}$

and transforms the right-hand side of the system (27) directly into the form
(33) with

$\mathrm{rank}(\partial_{\hat{z}_{k-1}}f_{k})=\dim(\hat{z}_{k-1})=\rho_{k}\,,\quad
k=1,\ldots,\bar{k}\,.$ (41)

However, the form (33) is not a usual system representation, since the
coordinates $\bar{x}^{+}$ on $\mathcal{X}^{+}$ are not shifted coordinates of
$\mathcal{X}\times\mathcal{U}$. If we want to perform the transformation (40)
also for the shifted variables, we have to give up the explicit system
representation as a map (3), and use an implicit system representation as
functions

$\begin{array}[]{cclcl}\bar{x}_{\bar{k}}^{i_{\bar{k}},+}-f_{\bar{k}}^{i_{\bar{k}}}(\bar{x},u)&=&0\,,&&i_{\bar{k}}=1,\ldots,\rho_{\bar{k}}\\\
&\vdots\\\
\bar{x}_{2}^{i_{2},+}-f_{2}^{i_{2}}(\bar{x},u)&=&0\,,&&i_{2}=1,\ldots,\rho_{2}\\\
\bar{x}_{1}^{i_{1},+}-f_{1}^{i_{1}}(\bar{x},u)&=&0\,,&&i_{1}=1,\ldots,\rho_{1}\end{array}$
(42)

on a manifold
$(\mathcal{X}^{+}\times\mathcal{U}^{+})\times(\mathcal{X}\times\mathcal{U})$
instead. Geometrically, the system equations (42) define a submanifold
$\mathcal{S}\subset(\mathcal{X}^{+}\times\mathcal{U}^{+})\times(\mathcal{X}\times\mathcal{U})$,
see [12] and [15]. Applying the transformation (40) with
$y_{\bar{k}}=(y_{\bar{k},1},y_{\bar{k},2})=(\bar{x}_{\bar{k}},\eta_{\bar{k}-1})$
to the equations of the implicit system representation (42) yields the
equations

$\begin{array}[]{cl}\Xi_{\bar{k}}:&y_{\bar{k},1}^{i_{\bar{k}},+}-f_{\bar{k}}^{i_{\bar{k}}}(y_{\bar{k}},\hat{z}_{\bar{k}-1})=0\\\
\Xi_{\bar{k}-1}:&\Phi_{\bar{k}-1}^{i_{\bar{k}-1}}(y_{\bar{k}}^{+},\hat{z}_{\bar{k}-1}^{+},y_{\bar{k}-1}^{+})\\\
&-f_{\bar{k}-1}^{i_{\bar{k}-1}}(y_{\bar{k}},\hat{z}_{\bar{k}-1},y_{\bar{k}-1},\hat{z}_{\bar{k}-2})=0\\\
\\\
\Xi_{2}:&\Phi_{2}^{i_{2}}(y_{\bar{k}}^{+},\hat{z}_{\bar{k}-1}^{+},y_{\bar{k}-1}^{+},\ldots,\hat{z}_{2}^{+},y_{2}^{+})\\\
&-f_{2}^{i_{2}}(y_{\bar{k}},\hat{z}_{\bar{k}-1},y_{\bar{k}-1},\ldots,\hat{z}_{2},y_{2},\hat{z}_{1})=0\\\
\Xi_{1}:&\Phi_{1}^{i_{1}}(y_{\bar{k}}^{+},\hat{z}_{\bar{k}-1}^{+},y_{\bar{k}-1}^{+},\ldots,\hat{z}_{1}^{+},y_{1}^{+})\\\
&-f_{1}^{i_{1}}(y_{\bar{k}},\hat{z}_{\bar{k}-1},y_{\bar{k}-1},\ldots,\hat{z}_{1},y_{1},\hat{z}_{0})=0\,,\end{array}$
(43)

which are clearly of the form (38).

##  6 Example

In this section, we demonstrate our results with the system

$\begin{array}[]{lcl}x^{1,+}&=&\tfrac{x^{2}+x^{3}+3x^{4}}{u^{1}+2u^{2}+1}\\\
x^{2,+}&=&x^{1}(x^{3}+1)(u^{1}+2u^{2}-3)+x^{4}-3u^{2}\\\
x^{3,+}&=&u^{1}+2u^{2}\\\ x^{4,+}&=&x^{1}(x^{3}+1)+u^{2}\,.\end{array}$ (44)

First, we show that the system is flat around the equilibrium
$(x_{0},u_{0})=(0,0)$ by computing the sequence of distributions (24) and
applying Theorem 9. In the first step of Algorithm 1, we have to calculate the
largest projectable subdistribution of the distribution

$E_{0}=\mathrm{span}\\{\partial_{u^{1}},\partial_{u^{2}}\\}\,.$

For this purpose, we introduce adapted coordinates (15) on
$\mathcal{X}\times\mathcal{U}$. After the transformation

$\begin{array}[]{ccl}\theta^{1}&=&f^{1}(x,u)\\\ \theta^{2}&=&f^{2}(x,u)\\\
\theta^{3}&=&f^{3}(x,u)\\\ \theta^{4}&=&f^{4}(x,u)\\\ \xi^{1}&=&x^{1}\\\
\xi^{2}&=&x^{3}\,,\end{array}$ (45)

the vector fields $\partial_{u^{1}}$ and $\partial_{u^{2}}$ are given by

$-\tfrac{\theta^{1}}{\theta^{3}+1}\partial_{\theta^{1}}+\xi^{1}(\xi^{2}+1)\partial_{\theta^{2}}+\partial_{\theta^{3}}$

and

$-2\tfrac{\theta^{1}}{\theta^{3}+1}\partial_{\theta^{1}}+(2\xi^{1}(\xi^{2}+1)-3)\partial_{\theta^{2}}+2\partial_{\theta^{3}}+\partial_{\theta^{4}}\,.$

Because of the presence of the fibre coordinates $\xi^{1}$ and $\xi^{2}$,
neither $\partial_{u^{1}}$ nor $\partial_{u^{2}}$ itself is projectable.
However, the linear combination $-2\partial_{u^{1}}+\partial_{u^{2}}$ reads in
adapted coordinates as

$-3\partial_{\theta^{2}}+\partial_{\theta^{4}}\,,$

and is therefore a projectable vector field. Thus, the largest projectable
subdistribution is given by

$D_{0}=\mathrm{span}\\{-2\partial_{u^{1}}+\partial_{u^{2}}\\}\,.$

The pushforward $f_{*}(D_{0})$ is the involutive distribution

$\Delta_{1}=\mathrm{span}\\{-3\partial_{x^{2,+}}+\partial_{x^{4,+}}\\}$

on $\mathcal{X}^{+}$ with $\dim(\Delta_{1})=\dim(D_{0})=1$. In the second
step, we have to determine the largest projectable subdistribution of

$E_{1}=\mathrm{span}\\{-3\partial_{x^{2}}+\partial_{x^{4}},\partial_{u^{1}},\partial_{u^{2}}\\}\,.$

In adapted coordinates (45), it can be verified that the complete distribution
is projectable, i.e., $D_{1}=E_{1}$. The pushforward $f_{*}(D_{1})$ is the
involutive distribution

$\begin{array}[]{cl}\Delta_{2}=\mathrm{span}\\{&-3\partial_{x^{2,+}}+\partial_{x^{4,+}},\\\
&\tfrac{x^{1,+}}{x^{3,+}+1}\partial_{x^{1,+}}-\partial_{x^{3,+}},\\\
&\tfrac{2x^{1,+}}{x^{3,+}+1}\partial_{x^{1,+}}-2\partial_{x^{3,+}}-\partial_{x^{4,+}}\\}\end{array}$

with $\dim(\Delta_{2})=\dim(D_{1})=3$. In the third step, we have to find the
largest projectable subdistribution of

$\begin{array}[]{cl}E_{2}=\mathrm{span}\\{&-3\partial_{x^{2}}+\partial_{x^{4}},\\\
&\tfrac{x^{1}}{x^{3}+1}\partial_{x^{1}}-\partial_{x^{3}},\\\
&\tfrac{2x^{1}}{x^{3}+1}\partial_{x^{1}}-2\partial_{x^{3}}-\partial_{x^{4}},\\\
&\partial_{u^{1}},\partial_{u^{2}}\\}\,.\end{array}$

In adapted coordinates (45), it can be verified that again the complete
distribution is projectable, i.e., $D_{2}=E_{2}$. The pushforward
$f_{*}(D_{2})$ is the involutive distribution

$\Delta_{3}=\mathrm{span}\\{\partial_{x^{1,+}},\partial_{x^{2,+}},\partial_{x^{3,+}},\partial_{x^{4,+}}\\}\,.$

Here we have $\dim(\Delta_{3})<\dim(D_{2})=5$. However, because of
$\dim(\Delta_{3})=n=4$ we can stop, and according to Theorem 9 the system (44)
is flat. It is important to emphasize that all these computations require only
the solution of algebraic equations, and can be performed efficiently with a
computer algebra program.

In the following, we calculate a flat output and transform the system into the
implicit triangular form (38). First, we straighten out the sequence (24) by a
state transformation of the form (26) with $\bar{x}_{1}=\bar{x}_{1}^{1}$,
$\bar{x}_{2}=(\bar{x}_{2}^{1},\bar{x}_{2}^{2})$, $\bar{x}_{3}=\bar{x}_{3}^{1}$
and $\dim(\bar{x}_{rest})=0$. With

$\begin{array}[]{ccl}\bar{x}_{3}^{1}&=&x^{1}(x^{3}+1)\\\
\bar{x}_{2}^{1}&=&x^{2}+3x^{4}\\\ \bar{x}_{2}^{2}&=&x^{3}\\\
\bar{x}_{1}^{1}&=&x^{4}\end{array}$

we get

$\begin{array}[]{ccl}\Delta_{1}&=&\mathrm{span}\\{\partial_{\bar{x}_{1}^{1,+}}\\}\\\
\Delta_{2}&=&\mathrm{span}\\{\partial_{\bar{x}_{1}^{1,+}},\partial_{\bar{x}_{2}^{1,+}},\partial_{\bar{x}_{2}^{2,+}}\\}\\\
\Delta_{3}&=&\mathrm{span}\\{\partial_{\bar{x}_{1}^{1,+}},\partial_{\bar{x}_{2}^{1,+}},\partial_{\bar{x}_{2}^{2,+}},\partial_{\bar{x}_{3}^{1,+}}\\}\,,\end{array}$

and the transformed system (27) is given by

$\begin{array}[]{ccl}\bar{x}_{3}^{1,+}&=&\bar{x}_{2}^{1}+\bar{x}_{2}^{2}\\\
\bar{x}_{2}^{1,+}&=&\bar{x}_{1}^{1}+\bar{x}_{3}^{1}(u^{1}+2u^{2})\\\
\bar{x}_{2}^{2,+}&=&u^{1}+2u^{2}\\\
\bar{x}_{1}^{1,+}&=&\bar{x}_{3}^{1}+u^{2}\,.\end{array}$ (46)

Constructing the coordinate transformation (40) by performing the procedure
from the proof of Theorem 9 yields

$\begin{array}[]{ccl}\bar{x}_{3}^{1}&=&y_{3}^{1}\\\
\bar{x}_{2}^{1}&=&y_{2}^{1}\\\ \bar{x}_{2}^{2}&=&\hat{z}_{2}^{1}-y_{2}^{1}\\\
\bar{x}_{1}^{1}&=&\hat{z}_{1}^{1}\\\
u^{1}&=&\hat{z}_{1}^{2}-2\hat{z}_{0}^{1}\\\
u^{2}&=&\hat{z}_{0}^{1}\,,\end{array}$ (47)

and straightens out the sequence (23) according to

$\begin{array}[]{ccl}D_{0}&=&\mathrm{span}\\{\partial_{\hat{z}_{0}^{1}}\\}\\\
D_{1}&=&\mathrm{span}\\{\partial_{\hat{z}_{0}^{1}},\partial_{\hat{z}_{1}^{1}},\partial_{\hat{z}_{1}^{2}}\\}\\\
D_{2}&=&\mathrm{span}\\{\partial_{\hat{z}_{0}^{1}},\partial_{\hat{z}_{1}^{1}},\partial_{\hat{z}_{1}^{2}},\partial_{y_{2}^{1}},\partial_{\hat{z}_{2}^{1}}\\}\,.\end{array}$

Applying the transformation (47) to the implicit version (42) of the system
(46) yields the implicit triangular form

$\begin{array}[]{cl}\Xi_{3}:&\begin{array}[]{c}y_{3}^{1,+}-\hat{z}_{2}^{1}=0\end{array}\\\
\Xi_{2}:&\begin{array}[]{l}y_{2}^{1,+}-y_{3}^{1}\hat{z}_{1}^{2}-\hat{z}_{1}^{1}=0\\\
\hat{z}_{2}^{1,+}-y_{2}^{1,+}-\hat{z}_{1}^{2}=0\end{array}\\\
\Xi_{1}:&\begin{array}[]{c}\hat{z}_{1}^{1,+}-y_{3}^{1}-\hat{z}_{0}^{1}=0\end{array}\end{array}$

with the flat output $y=(y_{3}^{1},y_{2}^{1})$. In original coordinates, the
flat output is given by $y=(x^{1}(x^{3}+1),x^{2}+3x^{4})$.

##  7 Conclusion

We have derived necessary and sufficient conditions for the flatness of
discrete-time systems. The conditions are based on a uniquely determined
sequence of distributions, and represent a straightforward generalization of
the well-known necessary and sufficient conditions for static feedback
linearizability. The computation of the sequence of distributions can be
performed efficiently in adapted coordinates, and requires only the solution
of algebraic equations. Therefore, it is well-suited for an implementation in
a computer algebra program. Furthermore, we have shown that every flat
discrete-time system can be transformed into a structurally flat implicit
triangular form.

##  Appendix A Appendix

###  A.1 Proof of Lemma 3

_Flatness of ( 11) $\Rightarrow$ Flatness of (10):_ If $y$ is a flat output of
the subsystem (11), then the system variables $x_{1}$, $x_{2}$, and $u_{1}$ of
this subsystem can be expressed as functions of $y$ and its forward-shifts.
Because of the regularity of the Jacobian matrix $\partial_{u_{2}}f_{2}$,
which is an immediate consequence of $\mathrm{rank}(\partial_{u}f)=\dim(u)$
and the structure of (10), the implicit function theorem allows to express
$u_{2}$ as function of $x_{1}$, $x_{2}$, $u_{1}$, and $x_{2}^{+}$.
Consequently, $u_{2}$ can also be expressed as a function of $y$ and its
forward-shifts, and $y$ is a flat output of the complete system (10).__
_Flatness of ( 10) $\Rightarrow$ Flatness of (11):_ Because of the regularity
of $\partial_{u_{2}}f_{2}$, we can perform an input transformation

$\hat{u}_{2}^{j_{2}}=f_{2}^{j_{2}}(x_{1},x_{2},u_{1},u_{2})\,,\quad
j_{2}=1,\ldots,m_{2}$

such that (10) takes the simpler form

$\begin{array}[]{lcl}x_{1}^{i_{1},+}=f_{1}^{i_{1}}(x_{1},x_{2},u_{1})\,,&&i_{1}=1,\ldots,n-m_{2}\\\
x_{2}^{i_{2},+}=\hat{u}_{2}^{i_{2}}\,,&&i_{2}=1,\ldots,m_{2}\,.\end{array}$
(48)

If

$y=\varphi(x_{1},x_{2},u_{1},\hat{u}_{2},u_{1,[1]},\hat{u}_{2,[1]},\ldots,u_{1,[q]},\hat{u}_{2,[q]})$

is a flat output of (48), then by substituting
$\hat{u}_{2}^{j_{2}}=x_{2,[1]}^{j_{2}}$ and
$\hat{u}_{2,[\alpha]}^{j_{2}}=x_{2,[\alpha+1]}^{j_{2}}\,,\,\alpha\geq 1$ we
immediately get a flat output of the subsystem (11).

###  A.2 Proof of Theorem 6

The proof is based on the identity (7). Differentiating both sides of (7) with
respect to $y_{[r_{s}]}^{s}$ for some arbitrary $s\in\\{1,\ldots,m\\}$ gives

$\partial_{y_{[r_{s}]}^{s}}\left(\delta_{y}(F_{x}^{i})\right)=\left(\partial_{u^{j}}f^{i}\circ
F\right)\partial_{y_{[r_{s}]}^{s}}F_{u}^{j}\,,\quad i=1,\ldots,n\,.$

Since $\delta_{y}$ only substitutes variables, shifting and differentiating
with respect to $y_{[r_{s}]}^{s}$ is equivalent to first differentiating with
respect to $y_{[r_{s}-1]}^{s}$ and shifting afterwards. Thus, we get the
equivalent identity

$\delta_{y}\left(\partial_{y_{[r_{s}-1]}^{s}}F_{x}^{i}\right)=\left(\partial_{u^{j}}f^{i}\circ
F\right)\partial_{y_{[r_{s}]}^{s}}F_{u}^{j}\,,\quad i=1,\ldots,n.$ (49)

Now let us consider this identity in coordinates $(x,u,u_{[1]},\ldots)$.
Substituting the relation

$\begin{array}[]{ccl}y&=&\varphi(x,u,u_{[1]},\ldots,u_{[q]})\\\
y_{[1]}&=&\delta_{xu}(\varphi(x,u,u_{[1]},\ldots,u_{[q]}))\\\
y_{[2]}&=&\delta_{xu}^{2}(\varphi(x,u,u_{[1]},\ldots,u_{[q]}))\\\ &\vdots\\\
y_{[R]}&=&\delta_{xu}^{R}(\varphi(x,u,u_{[1]},\ldots,u_{[q]}))\end{array}$
(50)

into (49) gives the identity

$\delta_{xu}(\tilde{w}^{i}(x,u,u_{[1]},\ldots))=(\partial_{u^{j}}f^{i})\tilde{v}^{j}(x,u,u_{[1]},\ldots)\,.$
(51)

The functions $\tilde{w}^{i}(x,u,u_{[1]},\ldots)$ and
$\tilde{v}^{j}(x,u,u_{[1]},\ldots)$ of (51) are obtained by substituting (50)
into the functions $\partial_{y_{[r_{s}-1]}^{s}}F_{x}^{i}$ and
$\partial_{y_{[r_{s}]}^{s}}F_{u}^{j}$ of (49). Note also that substituting
(50) into $\partial_{u^{j}}f^{i}\circ F$ yields just $\partial_{u^{j}}f^{i}$,
and that we have to replace the shift operator $\delta_{y}$ in $y$-coordinates
by the shift operator $\delta_{xu}$ in $(x,u)$-coordinates.

Evaluating the expression $\delta_{xu}(w^{i}(x,u,u_{[1]},\ldots))$ on the
left-hand side of (51) yields

$\tilde{w}^{i}(f(x,u),u_{[1]},u_{[2]},\ldots)=(\partial_{u^{j}}f^{i})\tilde{v}^{j}(x,u,u_{[1]},\ldots)\,.$
(52)

This identity holds (locally) for all values of $x,u,u_{[1]},\ldots$. If we
set the forward-shifts of $u$ that appear in (52) to suitable constant values

$\begin{array}[]{ccc}u_{[1]}&=&c_{1}\\\ u_{[2]}&=&c_{2}\\\ &\vdots\end{array}$
(53)

(for instance to $u_{0}$ from the equilibrium (4)), we finally get the
relation

$\tilde{w}^{i}(f(x,u),c_{1},c_{2},\ldots)=(\partial_{u^{j}}f^{i})\tilde{v}^{j}(x,u,c_{1},\ldots)\,.$
(54)

In fact, (54) is simply an evaluation of (52) on the subspace determined by
(53). With

$w^{i}(x^{+})=\tilde{w}^{i}(x^{+},c_{1},c_{2},\ldots)$ (55)

and

$v^{j}(x,u)=\tilde{v}^{j}(x,u,c_{1},\ldots)\,,$ (56)

the relation (54) can be written as

$w^{i}(x^{+})\circ f(x,u)=(\partial_{u^{j}}f^{i})v^{j}(x,u)\,,\quad
i=1,\ldots,n\,.$

Thus, the vector fields

$v=v^{j}(x,u)\partial_{u^{j}}$

on $\mathcal{X}\times\mathcal{U}$ and

$w=w^{i}(x^{+})\partial_{x^{i,+}}$

on $\mathcal{X}^{+}$ satisfy the condition (14) and are $f$-related.
Accordingly, the vector field $v$ is projectable and contained in the input
distribution $\mathrm{span}\\{\partial_{u}\\}$.

The first author and the second author have been supported by the Austrian
Science Fund (FWF) under grant number P 29964 and P 32151.

## References

  * [1] E. Aranda-Bricaire, Ü. Kotta, and C.H. Moog.  Linearization of discrete-time systems.  SIAM Journal on Control and Optimization, 34(6):1999–2023, 1996\.
  * [2] E. Aranda-Bricaire and C.H. Moog.  Linearization of discrete-time systems by exogenous dynamic feedback.  Automatica, 44(7):1707–1717, 2008.
  * [3] W.M. Boothby.  An Introduction to Differentiable Manifolds and Riemannian Geometry.  Academic Press, Orlando, 2nd edition, 1986.
  * [4] M. Fliess, J. Lévine, P. Martin, and P. Rouchon.  Sur les systèmes non linéaires différentiellement plats.  Comptes rendus de l’Académie des sciences. Série I, Mathématique, 315:619–624, 1992.
  * [5] M. Fliess, J. Lévine, P. Martin, and P. Rouchon.  Flatness and defect of non-linear systems: introductory theory and examples.  International Journal of Control, 61(6):1327–1361, 1995.
  * [6] M. Fliess, J. Lévine, P. Martin, and P. Rouchon.  A Lie-Bäcklund approach to equivalence and flatness of nonlinear systems.  IEEE Transactions on Automatic Control, 44(5):922–937, 1999.
  * [7] J.W. Grizzle.  Feedback linearization of discrete-time systems.  In A. Bensoussan and J.L. Lions, editors, Analysis and Optimization of Systems, volume 83 of Lecture Notes in Control and Information Sciences, pages 273–281. Springer, Berlin, 1986.
  * [8] J.W. Grizzle.  A linear algebraic framework for the analysis of discrete-time nonlinear systems.  SIAM Journal on Control and Optimization, 31(4):1026–1044, 1993\.
  * [9] B. Jakubczyk.  Feedback linearization of discrete-time systems.  Systems & Control Letters, 9(5):411–416, 1987.
  * [10] B. Jakubczyk and W. Respondek.  On linearization of control systems.  Bull. Acad. Polonaise Sci. Ser. Sci. Math., 28:517–522, 1980.
  * [11] A. Kaldmäe and Ü. Kotta.  On flatness of discrete-time nonlinear systems.  In Proceedings 9th IFAC Symposium on Nonlinear Control Systems (NOLCOS), pages 588–593, 2013.
  * [12] B. Kolar.  Contributions to the Differential Geometric Analysis and Control of Flat Systems.  Shaker Verlag, Aachen, 2017.
  * [13] B. Kolar, A. Kaldmäe, M. Schöberl, Ü. Kotta, and K. Schlacher.  Construction of flat outputs of nonlinear discrete-time systems in a geometric and an algebraic framework.  In Proceedings 10th IFAC Symposium on Nonlinear Control Systems (NOLCOS), pages 808–813, 2016.
  * [14] B. Kolar, M. Schöberl, and J. Diwold.  Differential-geometric decomposition of flat nonlinear discrete-time systems.  arXiv e-prints, 2019.  arXiv:1907.00596 [math.OC].
  * [15] B. Kolar, M. Schöberl, and K. Schlacher.  A decomposition procedure for the construction of flat outputs of discrete-time nonlinear control systems.  In Proceedings 22nd International Symposium on Mathematical Theory of Networks and Systems (MTNS), pages 775–782, 2016.
  * [16] Ü. Kotta.  Inversion Method in the Discrete-time Nonlinear Control Systems Synthesis Problems, volume 205 of Lecture Notes in Control and Information Sciences.  Springer, Berlin, 1995.
  * [17] H. Nijmeijer and A.J. van der Schaft.  Nonlinear Dynamical Control Systems.  Springer, New York, 1990.
  * [18] P. Rouchon.  Necessary condition and genericity of dynamic feedback linearization.  Journal of Mathematical Systems, Estimation, and Control, 4(2):1–14, 1994.
  * [19] D.J. Saunders.  The Geometry of Jet Bundles.  Cambridge University Press, Cambridge, 1989.
  * [20] M. Schöberl.  Contributions to the Analysis of Structural Properties of Dynamical Systems in Control and Systems Theory - A Geometric Approach.  Shaker Verlag, Aachen, 2014.
  * [21] M. Schöberl and K. Schlacher.  On an implicit triangular decomposition of nonlinear control systems that are 1-flat - a constructive approach.  Automatica, 50:1649–1655, 2014.
  * [22] H. Sira-Ramirez and S.K. Agrawal.  Differentially Flat Systems.  Marcel Dekker, New York, 2004.
  * [23] A.J. van der Schaft.  Linearization and input-output decoupling for general nonlinear systems.  Systems & Control Letters, 5:27–33, 1984.