Linearity of PCA PCA is considered a linear procedure, however:
$$\mathrm{PCA}(X)\neq \mathrm{PCA}(X_1)+\mathrm{PCA}(X_2)+\ldots+\mathrm{PCA}(X_n),$$
where  $X=X_1+X_2+\ldots+X_n$. This is to say that the eigenvectors obtained by the PCAs on the data matrices $X_i$ do not sum up to equal the eigenvectors obtained by PCA on the sum of the data matrices $X_i$. But isn't the definition of a linear function $f$ that:
$$f(x+y)=f(x)+f(y)?$$
So why is PCA considered "linear" if it does not satisfy this very basic condition of linearity?
 A: "Linear" can mean many things, and is not exclusively employed in a formal manner.
PCA is not often defined as a function in the formal sense, and therefore it is not expected to fulfill the requirements of a linear function when described as such. It is more often described, as you said, as a procedure, and sometimes an algorithm (although I don't like this last option). It is often said to be linear in an informal, not well-defined way.
PCA can be considered linear, for instance, in the following sense. It belongs to a family of methods that consider that each variable $X_i$ can be approximated by a  function 
$$
X_i \approx f_Y(\alpha)
$$
where $\alpha \in \mathbb{R}^k$ and $Y$ is a set of $k$ variables with some desirable property. In the case of PCA, $Y$ is a set of independent variables that can be reduced in cardinality with minimal loss in approximation accuracy in a specific sense. Those are desirable properties in numerous settings.
Now, for PCA, each $f_i$ is restricted to the form
$$
f_Y(\alpha) = \sum_{i=1}^k \alpha_{i}Y_i
$$
that is, a linear combination of the variables in $Y$.
Given this restriction, it offers a procedure to find the optimal (in some sense) values of $Y$ and the $\alpha_{ij}$'s.   That is, PCA only considers linear functions as plausible hypotheses. In this sense, I think it can be legitimately described as "linear".
A: PCA provides/is a linear transformation. 
If you take the map associated with a particular analysis, say $\mathbf{M} \equiv  PCA(X_1 + X_2)$ then $\mathbf{M}(X_1+X_2) = \mathbf{M}(X_1) + \mathbf{M}(X_2)$.
The culprit is that $PCA(X_1 + X_2)$, $PCA(X_1)$ and $PCA(X_2)$ are not the same linear transformations. 

As a comparison a very simple example of a process that uses a linear transformation but is not a linear transformation itself:
The rotation $D(\mathbf{v})$ that doubles the angle of a vector $\mathbf{v}$ (say a point in 2-d euclidian space) with some reference vector (say $\left[x,y\right]=\left[1,0\right]$), is not a linear transformation. For example
$D(\left[1,1\right]) \rightarrow \left[0,\sqrt{2}\right]$  
and
$D(\left[0,1\right]) \rightarrow \left[-1,0\right]$ 
but
$D(\left[1,1\right]+\left[0,1\right]=\left[1,2\right]) \rightarrow \left[-0.78,2.09\right] \neq \left[-1,\sqrt{2}\right]$
this doubling of the angle, which involves calculation of angles, is not linear, and is analogous to the statement of amoeba, that the calculation of eigenvector is not linear
A: When we say that PCA is a linear method, we refer to the dimensionality reducing mapping $f:\mathbf x\mapsto \mathbf z$ from high-dimensional space $\mathbb R^p$ to a lower-dimensional space $\mathbb R^k$. In PCA, this mapping is given by multiplication of $\mathbf x$ by the matrix of PCA eigenvectors and so is manifestly linear (matrix multiplication is linear): $$\mathbf z = f(\mathbf x) = \mathbf V^\top \mathbf x.$$ This is in contrast with nonlinear methods of dimensionality reduction, where the dimensionality reducing  mapping can be nonlinear.
On the other hand, the $k$ top eigenvectors $\mathbf V\in \mathbb R^{p\times k}$ are computed from the data matrix $\mathbf X\in \mathbb R^{n\times p}$ using what you called $\mathrm{PCA}()$ in your question: $$\mathbf V = \mathrm{PCA}(\mathbf X),$$
and this mapping is certainly non-linear: it involves computing eigenvectors of the covariance matrix, which is a non-linear procedure. (As a trivial example, multiplying $\mathbf X$  by $2$ increases the covariance matrix by $4$, but its eigenvectors stay the same as they are normalized to have unit length.)
