  We consider composition orderings for linear functions of one variable. Given
$n$ linear functions $f_1,\dots,f_n$ and a constant $c$, the objective is to
find a permutation $\sigma$ that minimizes/maximizes
$f_{\sigma(n)}\circ\dots\circ f_{\sigma(1)}(c)$. It was first studied in the
area of time-dependent scheduling, and known to be solvable in $O(n\log n)$
time if all functions are nondecreasing. In this paper, we present a complete
characterization of optimal composition orderings for this case, by regarding
linear functions as two-dimensional vectors. We also show several interesting
properties on optimal composition orderings such as the equivalence between
local and global optimality. Furthermore, by using the characterization above,
we provide a fixed-parameter tractable (FPT) algorithm for the composition
ordering problem for general linear functions, with respect to the number of
decreasing linear functions. We next deal with matrix multiplication orderings
as a generalization of composition of linear functions. Given $n$ matrices
$M_1,\dots,M_n\in\mathbb{R}^{m\times m}$ and two vectors $w,y\in\mathbb{R}^m$,
where $m$ denotes a positive integer, the objective is to find a permutation
$\sigma$ that minimizes/maximizes $w^\top M_{\sigma(n)}\dots M_{\sigma(1)} y$.
The problem is also viewed as a generalization of flow shop scheduling through
a limit. By this extension, we show that the multiplication ordering problem
for $2\times 2$ matrices is solvable in $O(n\log n)$ time if all the matrices
are simultaneously triangularizable and have nonnegative determinants, and FPT
with respect to the number of matrices with negative determinants, if all the
matrices are simultaneously triangularizable. As the negative side, we finally
prove that three possible natural generalizations are NP-hard: 1) when $m=2$,
2) when $m\geq 3$, and 3) the target version of the problem.
