Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[Problem proposal] Adjugate matrix #1269

Closed
adamant-pwn opened this issue Oct 27, 2024 · 3 comments · Fixed by #1270
Closed

[Problem proposal] Adjugate matrix #1269

adamant-pwn opened this issue Oct 27, 2024 · 3 comments · Fixed by #1270
Labels
work in progress 担当者が決定した

Comments

@adamant-pwn
Copy link
Contributor

Problem name: Adjugate matrix
(Optional) Problem ID: adjugate_matrix

Problem

Given $N \times N$ matrix $A = \lbrace a_{ij} \rbrace$ with entries in $\mathbb{Z}/p\mathbb{Z}$, print $\text{adj } A = \lbrace (-1)^{i+j}M_{ji} \rbrace$, where $M_{ij}$ is the determinant of the matrix that is obtained from $A$ by removing its $i$-th row and $j$-th column.

Constraint

  • $1 \leq N \leq 500$

Solution / Reference

  • All solutions rely on $A \text{ adj }A = I_n \det A$. Wiki article:
    • If $A$ is invertible, then $\text{adj }A = A^{-1} \det A$;
    • If $\text{rank }A < n-1$, then $\text{adj }A = 0$;
    • If $\text{rank }A = n-1$, then $\text{adj }A = \alpha xy^\top$, where $Ax = 0$ and $A^\top y = 0$. Find $\alpha$ by finding any non-zero $M_{ij}$.
  • Can also be found via Schur's complement by embedding $A$ into an invertible matrix or via Frobenius normal form.

(Optional) Input

$N$
$a_{11}$ $a_{12}$ ... $a_{1N}$
$a_{21}$ $a_{22}$ ... $a_{2N}$
:
$a_{N1}$ $a_{N2}$ ... $a_{NN}$

(Optional) Output

$b_{11}$ $b_{12}$ ... $b_{1N}$
$b_{21}$ $b_{22}$ ... $b_{2N}$
:
$b_{N1}$ $b_{N2}$ ... $b_{NN}$

$b_{ij} = (-1)^{i+j} M_{ji}$.

(Optional) Note / Disucussion

  • Was used in Swiss Subregional Contest 2024 (problem A), no solves though.
  • Can reuse matrix inverse as a base, but need to add a few corner $\text{rank }A = n-1$ test cases.
@maspypy
Copy link
Collaborator

maspypy commented Oct 27, 2024

Thank you very much!
A few years ago, I personally thought about this problem but couldn't find a solution for the case where rank == n-1. I'll review the method within the next few days and also check the pull request.

@adamant-pwn
Copy link
Contributor Author

Thanks! I initially only came up with some complicated approaches via Frobenius normal form or Schur's complement (the latter is actually quite easy to implement, which is why the PR uses it, but a bit harder to explain), but then a tester pointed out that Wikipedia contained all the information you need all along with the $\text{adj }A = \alpha xy^\top$ representation 😅

For the solution that is used in the pull request, I can also share this brief tutorial PDF: matrix-minors-r16-en.pdf

@hos-lyric
Copy link
Collaborator

It will be nice to have this problem on Library Checker!

$\mathrm{adj}(A)$ can be found by tranposing the linear map $B \mapsto [x^1] \det(A+Bx) = \mathrm{tr}(\mathrm{adj}(A) B)$ (the last equality is https://en.wikipedia.org/wiki/Jacobi%27s_formula). I learned this from EntropyIncreaser.

Also, this problem is related and some other methods might be found in the submissions: https://atcoder.jp/contests/xmascon21/tasks/xmascon21_h

@maspypy maspypy added the work in progress 担当者が決定した label Oct 28, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
work in progress 担当者が決定した
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants