Page 15 of the Keccak reference (PDF) explains that the $Chi$ step mapping of the Keccak-f permutation in Keccak is defined to be “nonlinear mapping”. Without this, the complete permutation would be linear.
What does ”nonlinear” mean? The paper says that $Chi$ has algebraic degree of 2, so it is not a linear function. But now I have to explain why $Chi$ has exactly algebraic degree 2. I found this question Non-linearity of a boolean function which helped me a little bit. But I am still not sure if understand this correct:
A linear boolean function $y = ax + bz + c$ is a linear function with $y$ as output bit, $x$ and $z$ as input variable and $a$, $b$ and $c$ are constants. The variables are only multiplicated by the constants (I guess the addition and multiplication of a boolean function are defined in $GF(2)$ isn't it?)
So, a non linear boolean function is something like $y = axz + bx + c$. $x$ and $z$ are variables and the term $axz$ contains two variables, which describes the degree of $2$ in this example.
Now, the $Chi$ step mapping function is described formal as:
$a[x] <- a[x] + (a[x+1] + 1)*a[x+2]$
If we say that a[x], a[x+1] and a[x+2] is the input variables for a function like this:
$f(x, y, z) = x + (y+1)z$
we have a a degree of two in the term $(y+1)z$.
