Electric Dipole Moments (EDMs) of electrons, neutrons or nuclei are sensitive probes for new physics beyond the Standard Model of particle physics. In the present project we propose to measure the electron EDM using embedded particles in a cryogenic solid matrix of rare gas or hydrogen. Matrices offer unprecedented sample sizes while maintaining many characteristics of an atomic physics experiment, such as manipulation by lasers. An EDM experiment on atoms and molecules in inert gas matrices has the potential to reach a statistical sensitivity in the order of 10-36e.cm; a value several orders of magnitude beyond that of any other proposed technique. In a strong collaboration between experimental (LAC, ISMO,LPL) and theoretical (CIMAP) groups, we seek to perform a detailed investigation of all limiting effects (trapping site dependence of optical pumping and coherence times mainly) using metal atoms (Cs typically) in argon and parahydrogen matrices in view of a first proof of principle EDM measurement. This will pave the way toward unprecedented sensitivity.