We introduce a necessary and sufficient criterion for the non-Markovianity of Gaussian quantum dynamical maps based on the violation of divisibility. The criterion is derived by defining a general vectorial representation of the covariance matrix whi
ch is then exploited to determine the condition for the complete positivity of partial maps associated to arbitrary time intervals. Such construction does not rely on the Choi-Jamiolkowski representation and does not require optimization over states.
