The paper presents realization theory of discrete-time linear switched systems. We present necessary and sufficient conditions for an input output map to admit a discrete-time linear switched system realization. In addition, we present a characterization of minimality of discrete-time linear switched systems in terms of reachability and observability. Further, we prove that minimal realizations are unique up to isomorphism. We also discuss algorithms for converting a linear switched system to a minimal one and for constructing a state-space representation from input output data. The paper uses the theory of rational formal power series in non-commutative variables. (C) 2013 Elsevier Ltd. All rights reserved.