  We develop a theory of linear witnesses for detecting non-Markovianity, based
on the geometric structure of the set of Choi states for all Markovian
evolutions having Lindblad type generators. We show that the set of all such
Markovian Choi states form a convex and compact set under the small time
interval approximation. Invoking geometric Hahn-Banach theorem, we construct
linear witnesses to separate a given non-Markovian Choi state from the set of
Markovian Choi states. We present examples of such witnesses for dephasing
channel and Pauli channel in case of qubits. We further investigate the
geometric structure of the Markovian Choi states to find that they do not form
a polytope. This presents a platform to consider non-linear improvement of
non-Markovianity witnesses.
