jo, sollte mit PartitionMagic einwandfrei gehen... einfach aus dem freien Speicherplatz auf einer der Partitionen ne neue Partition machen.
Für Linux brauchst du eine Swap-Partition (~500 MB sollten vollkommen ausreichen), eine Ext2-(Linux Native)Partition wo das Linux draufkommt und eine Boot-Partition. Für die Bootpartition reichen 50 MB normalerweise auch, sehr oft ist die Bootpartition einfach die Ext2-partition (mit dem linux drauf), wo einfach das "Bootable"-flag gesetzt ist.
kurz... du kannst linux nicht auf eine normale windows-(also fat(32))partition installieren, sondern brauchst eine, besser mehrere neue partitionen die du am besten mit PartitionMagic erstellst. Formatieren musst du die Partitionen noch nicht mit PM, mandrake sollte dazu selbst in der lage sein

schau dir mal den befehl "fdisk" an.
mfg para