Please draw a schematic. A bad pencil sketch photographed with a phone is better than trying to use words.
I suspect that you will need a PNP transistor to switch the positive power to the GPS. Switching the negative is a bad idea as it's still connected to the Arduino inputs.