Родился 2 ноября 1917 года в деревне Ключи ныне Казачинско-Ленского района Иркутской области в крестьянской семье.
Окончил педагогическое училище.
С 1937 года в Военно-Морском Флоте. Окончил военно-морское училище.
Участник Великой Отечественной войны с июня 1941 года.
Командир звена 2-й бригады торпедных катеров старший лейтенант Подымахин М. П. в 1943 году успешно наносил удары по портам Камыш-Бурун, Феодосия, в блокаде акваторий от Анапы до Керченского пролива, провёл 18 боёв с торпедными катерами противника у селения Мысхако. Во время штурма Новороссийска первым высадил десант и обеспечил прорыв остальных катеров в порт. 7 мая 1944 года в бою под Севастополем потопил вражескую десантную баржу.
Указом Президиума Верховного Совета СССР от 5 ноября 1944 года за образцовое выполнение боевых заданий командования и проявленные при этом геройство и мужество старшему лейтенанту Подымахину Матвею Прокопьевичу присвоено звание Героя Советского Союза с вручением ордена Ленина и медали «Золотая Звезда».
После войны служил на Тихоокеанском флоте.
В 1958 году он окончил Курсы усовершенствования офицерского состава при Военно-морской академии.
С 1973 года капитан 1-го ранга Подымахин М. П. — в запасе, а затем в отставке.
Жил в городе-герое Ленинград, где и скончался 17 февраля 1993 года. Похоронен на Серафимовском кладбище (Кленовый участок).
Награждён орденом Ленина, 3 орденами Красного Знамени, орденом Отечественной войны 1-й степени, 2 орденами Красной Звезды, медалями.
Бюст Героя установлен в Севастополе на территории Черноморского ВВМУ имени П. С. Нахимова, а также на территории бригады ракетных катеров в г. Севастополь, бухта Карантинная