Друзья! Подскажите пожалуйста, почему при заполнении матрицы Python изменяется полностью столбец.

Потому, что:

 a = [...] * n
a_new = [...] * (n + 1) 

Ты создаёшь массивы не из отдельных векторов, а из указателей на один и тот же вектор. Но в первом случае это не проявляется, т.к. ты сразу же уничтожаешь созданные строки матрицы, присваивая на их место результаты list(map(...)).

Можно решить проблему так:

 a = [list(map(int, stdin.readline().split())) for _ in range(n)]

a_new = [[0] * (m + 1) for _ in range(n + 1)]