характеристический полином как функция элементов матрицы

[maxal]

Пусть $n$ - натуральное число. Рассмотрим матрицы $n\times n,$ элементами которых являются одни и те же $n^2$ переменных $x_1, \dots, x_{n^2}$.
Доказать или опровергнуть, что характеристические полиномы (суть функции от $x_1, \dots, x_{n^2}$ и $\lambda$) двух таких матриц совпадают тогда и только тогда, когда одна матрица может быть получена из другой одновременной перестановкой строк и столбцов и возможным последующим транспонированием.

Просьба обязательно выкладывать ссылки на готовые решения, если таковые существуют

[Macavity]

maxal писал(а):

Пусть $n$ - натуральное число. Рассмотрим матрицы $n\times n,$ элементами которых являются одни и те же $n^2$ переменных $x_1, \dots, x_{n^2}$.
Доказать или опровергнуть, что характеристические полиномы (суть функции от $x_1, \dots, x_{n^2}$ и $\lambda$) двух таких матриц совпадают тогда и только тогда, когда одна матрица может быть получена из другой одновременной перестановкой строк и столбцов и возможным последующим транспонированием.

Просьба обязательно выкладывать ссылки на готовые решения, если таковые существуют

Хороший вопрос.
Вероятно, связан с изоморфизмом двух графов...
Не слишком ли "прост" как для олимпиадных задач...

[juna]

Достаточность доказать просто.
Действительно, как отмечалось, можно использовать результаты теории графов.
Пусть матрица $A$ заполнена произвольными натуральными числами, тогда ее можно трактовать как матрицу смежности некоторого орграфа с кратными дугами.
Известно, что указанное преобразование приводит к изоморфным графам (т.е. к такому же графу, у которого просто переобозначены вершины).
Известно также, что данное преобразование не меняет значение определителя, так как перестановка строк меняет на $-1$ и перестановка столбцов меняет на $-1$.
Отсюда сразу следует, что у изоморфных графов значение определителя от матрицы смежности - одно число.
Если мы ищем характеристический многочлен, то вычитаем $\lambda$ по главной диагонали, при этом в ходе преобразования элементы главной диагонали только переставляются, но не меняются. Значит, если придать $\lambda$ любое значение, то $A-\lambda E$ задает граф, изоморфный $A^{pr}-\lambda E$.

[Руст]

maxal писал(а):

Пусть $n$ - натуральное число. Рассмотрим матрицы $n\times n,$ элементами которых являются одни и те же $n^2$ переменных $x_1, \dots, x_{n^2}$.
Доказать или опровергнуть, что характеристические полиномы (суть функции от $x_1, \dots, x_{n^2}$ и $\lambda$) двух таких матриц совпадают тогда и только тогда, когда одна матрица может быть получена из другой одновременной перестановкой строк и столбцов и возможным последующим транспонированием.

Просьба обязательно выкладывать ссылки на готовые решения, если таковые существуют

Очевидно, что необходимость неверна. Характеристические многочлены A и CAC^{-1} одни и те же, однако не всякое сопряжение с С можно получить только элементарными преобразованиями перестановок. Например, это неверно для $C=\dbinom{1 \ \ 1}{0 \ \ 1}$.

[незваный гость]

Руст писал(а):

Очевидно, что необходимость неверна.

Мне по-прежнему не очевидно. В частности, неочевидно, что существует $C$ оставляющее множество элементов без изменения.

Более того, я готов утверждать, что для $ n \leq 3 $ это утверждение верно. Желающие опровергнуть должны представить аргументы, оставляющие малые измерения как исключения.

P.S. Если мы зафиксируем диагональные элементы, мы тем самым сведем задачу к перестановкам остальных (с точностью до транспонирования), что не в пример приятнее.

[Руст]

Существуют уже двумерные матрицы с двумя разными корнями, т.е. приводящиеся к диагональному виду. Ясно, что из диагональной матрицы, только перестановками не получишь исходную не диагональную матрицу. Если всё ещё не очевидно приведу конкретный пример взяв характеристический многочлен (x-1)(x-2)=x^2-3x+2 $A=\dbinom{1 \ 1}{0 \ 2}$

[juna]

У $A$ и $CAC^{-1}$ действительно будут одинаковые характеристические полиномы, но $A\not =CAC^{-1}$ и $CAC^{-1}$ не может быть получено перестановками в $A$, потому что там совсем другие числа. И вот здесь нужно уточнить условие задачи:

maxal писал(а):

Рассмотрим матрицы $n*n$ элементами которых являются одни и те же $n^2$ переменных $x_1,...x_{n^2}$.

[Руст]

Артамонов Ю.Н. писал(а):

У $A$ и $CAC^{-1}$ действительно будут одинаковые характеристические полиномы, но $A\not =CAC^{-1}$ и $CAC^{-1}$ не может быть получено перестановками в $A$, потому что там совсем другие числа. И вот здесь нужно уточнить условие задачи:

maxal писал(а):

Рассмотрим матрицы $n*n$ элементами которых являются одни и те же $n^2$ переменных $x_1,...x_{n^2}$.

Но, если это понимать так, что матрицы состоят из одних и тех же элементов, то всё равно это неверно, только размерность необходимо увеличить. Расмотрим матрицы, у которых диагональные элементы 1,2,...,n. Ниже диагонали нули, выше диагонали числа n+1,n+2,...n(n+1)/2. У всех этих матриц характеристический полином (x-1)(x-2)...(x-n). Однако количество преобразований maxala всего 2*n!n!, в то время как количество возможных расстановок с заданным характеристическим мнгочленом больше, чем (n(n-1)/2)! - явно больше 2*n!n!. Т.е. всё ещё очевидно, только для больших n.

[RIP]

Руст, элементы матрицы - не конкретные числа, а $n^2$ независимых переменных. Прочитайте еще раз внимательно вот это

maxal писал(а):

...характеристические полиномы (суть функции от $x_1, \dots, x_{n^2}$ и $\lambda$)...

[Руст]

RIP писал(а):

Руст, элементы матрицы - не конкретные числа, а $n^2$ независимых переменных. Прочитайте еще раз внимательно вот это

maxal писал(а):

...характеристические полиномы (суть функции от $x_1, \dots, x_{n^2}$ и $\lambda$)...

Тогда очевидно, что это необходимое условие. Тут достаточно совпадение свободного коэффициента, т.е. детерминанта и легко доказать по индукции, разлагая по какому нибудь столбцу или строке.

[juna]

RIP, а вот теперь мне непонятно, как Вы эти функции себе представляете. Какая разница, если при любых конкретных значениях этих переменных рассуждения Руста проходят?
По-моему, maxal имел в виду все-таки числа.

[RIP]

Артамонов Ю.Н.
Для простоты рассмотрим $n=3$. Рассматриваются матрицы вида

$$A=\begin{pmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\end{pmatrix},$$

где $a_{ij}$ - перестановка букв $x_1,\ldots,x_9$. Тогда $\det(A-\lambda E)$ - функция от $x_1,\ldots,x_9,\lambda$

[Руст]

Артамонов Ю.Н. писал(а):

RIP, а вот теперь мне непонятно, как Вы эти функции себе представляете. Какая разница, если при любых конкретных значениях этих переменных рассуждения Руста проходят?
По-моему, maxal имел в виду все-таки числа.

Не при любых. Я брал ниже диагонали нули.
Только, мне всё равно кажется, что задача не имеет никакого интереса. Так как не требуется совпадение всего многочлена (как функции), достаточно совпадения свободного коэффициента, т.е. детерминанта.

[незваный гость]

Скажем так: для произвольных матриц (без ограничений типа нули ниже диагонали), я готов утверждать, что характеристические полиномы совпадут тогда и только тогда, когда совпадут определители.

[Руст]

Да, при совпадении определителя как функции n^2 переменных.