text: Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×
  
  Sherman Morrison Formula
  
  Правка en10, от McDic, 2020-02-22 16:42:59
  
  ### Introduction
  
  Hello. I would like to share some nice stuff, called Sherman-Morrison formula. If you know this formula, it's easier to understand how BFGS update works in convex optimization and machine learning. But in this topic, we will just simply focus on this formula and learn how to calculate inverse matrix of rank-$1$ updated invertible matrix faster.
  
  The motivation of this post is that my problem using Sherman Morrison formula is rejected by multiple coordinators.
  
  ### Definition
  
  You have invertible $\mathbb{R}^{n \times n}$ matrix $A$, and $\mathbb{R}^{n}$ vectors $u$ and $v$. Then $(A + uv^{T})^{-1} = A^{-1} - \frac{A^{-1}uv^{T}A^{-1}}{v^{T}A^{-1}u + 1}$. If $v^{T}A^{-1}u = -1$, then $A + uv^{T}$ is non-invertible.
  
  ### Time complexity
  
  You can calculate Sherman Morrison formula in $O(n^2)$, because $A^{-1}u$, $v^{T}A^{-1}$ are vector.
  
  Normally you need $O(n^3)$ time complexity to calculate inverse matrix except for some special matrix(diagonal matrix etc). But, since you can calculate Sherman-Morrison formula in $O(n^2)$, if you find some matrix can be represented as rank-$1$ updated matrix of special matrix, you can calculate inverse of that matrix in $O(n^2)$.
  
  ### Generalization
  
  There is a generalization of this formula called Woodbury Matrix Identity.
  
  ### Sample problem
  
  This problem is that rejected problem.
  
  You have matrix $A = \begin{bmatrix} 1 & 2 & \cdots & n \\ n+1 & n+2 & \cdots & 2n \\ \cdots & \cdots & \cdots & \cdots \\ n^{2}-n+1 & n^{2}-n+2 & \cdots & n^{2} \end{bmatrix} + diag(c_{1}, c_{2}, \ldots, c_{n})$.
  
  In $i$-th query, you will select any row or column of $A$ and multiply this by $x_{i}$. Compute $A^{-1}$ if $A$ is invertible after each query.
  
  Constraints: $2 \le n \le 200$, $1 \le q \le 200$, $0 \lt c_{i}$, $x_{i} \neq 0$.
  
  #### История
  
  Правки
  
  Rev. Язык Кто Когда Δ Комментарий
  en10 McDic 2020-02-22 16:42:59 10
  en9 McDic 2020-02-22 12:15:12 14
  en8 McDic 2020-02-22 12:14:58 6
  en7 McDic 2020-02-22 10:48:12 68
  en6 McDic 2020-02-22 10:45:43 21
  en5 McDic 2020-02-22 10:43:42 16
  en4 McDic 2020-02-22 10:43:04 158
  en3 McDic 2020-02-22 10:39:15 42
  en2 McDic 2020-02-22 10:38:16 105 (published)
  en1 McDic 2020-02-22 10:31:33 1826 Initial revision (saved to drafts)
explanation: The document is a detailed explanation of the Sherman Morrison Formula, which is used to calculate the inverse of a rank-1 updated invertible matrix. It includes an introduction, definition, time complexity analysis, generalization, and a sample problem. The sample problem describes a matrix and a series of queries, asking for the computation of the inverse of the matrix after each query. The document contains a question in the form of a sample problem but does not provide an answer to it.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×
  
  Sherman Morrison Formula
  
  Правка en10, от McDic, 2020-02-22 16:42:59
  
  ### Introduction
  
  Hello. I would like to share some nice stuff, called Sherman-Morrison formula. If you know this formula, it's easier to understand how BFGS update works in convex optimization and machine learning. But in this topic, we will just simply focus on this formula and learn how to calculate inverse matrix of rank-$1$ updated invertible matrix faster.
  
  The motivation of this post is that my problem using Sherman Morrison formula is rejected by multiple coordinators.
  
  ### Definition
  
  You have invertible $\mathbb{R}^{n \times n}$ matrix $A$, and $\mathbb{R}^{n}$ vectors $u$ and $v$. Then $(A + uv^{T})^{-1} = A^{-1} - \frac{A^{-1}uv^{T}A^{-1}}{v^{T}A^{-1}u + 1}$. If $v^{T}A^{-1}u = -1$, then $A + uv^{T}$ is non-invertible.
  
  ### Time complexity
  
  You can calculate Sherman Morrison formula in $O(n^2)$, because $A^{-1}u$, $v^{T}A^{-1}$ are vector.
  
  Normally you need $O(n^3)$ time complexity to calculate inverse matrix except for some special matrix(diagonal matrix etc). But, since you can calculate Sherman-Morrison formula in $O(n^2)$, if you find some matrix can be represented as rank-$1$ updated matrix of special matrix, you can calculate inverse of that matrix in $O(n^2)$.
  
  ### Generalization
  
  There is a generalization of this formula called Woodbury Matrix Identity.
  
  ### Sample problem
  
  This problem is that rejected problem.
  
  You have matrix $A = \begin{bmatrix} 1 & 2 & \cdots & n \\ n+1 & n+2 & \cdots & 2n \\ \cdots & \cdots & \cdots & \cdots \\ n^{2}-n+1 & n^{2}-n+2 & \cdots & n^{2} \end{bmatrix} + diag(c_{1}, c_{2}, \ldots, c_{n})$.
  
  In $i$-th query, you will select any row or column of $A$ and multiply this by $x_{i}$. Compute $A^{-1}$ if $A$ is invertible after each query.
  
  Constraints: $2 \le n \le 200$, $1 \le q \le 200$, $0 \lt c_{i}$, $x_{i} \neq 0$.
  
  #### История
  
  Правки
  
  Rev. Язык Кто Когда Δ Комментарий
  en10 McDic 2020-02-22 16:42:59 10
  en9 McDic 2020-02-22 12:15:12 14
  en8 McDic 2020-02-22 12:14:58 6
  en7 McDic 2020-02-22 10:48:12 68
  en6 McDic 2020-02-22 10:45:43 21
  en5 McDic 2020-02-22 10:43:42 16
  en4 McDic 2020-02-22 10:43:04 158
  en3 McDic 2020-02-22 10:39:15 42
  en2 McDic 2020-02-22 10:38:16 105 (published)
  en1 McDic 2020-02-22 10:31:33 1826 Initial revision (saved to drafts)
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The document is a detailed explanation of the Sherman Morrison Formula, which is used to calculate the inverse of a rank-1 updated invertible matrix. It includes an introduction, definition, time complexity analysis, generalization, and a sample problem. The sample problem describes a matrix and a series of queries, asking for the computation of the inverse of the matrix after each query. The document contains a question in the form of a sample problem but does not provide an answer to it.
  
  Label: question