### McDic's blog

By McDic, history, 6 weeks ago, ,

### 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$.

• +6

 » 6 weeks ago, # |   0 orz
 » 6 weeks ago, # |   +32 McDic orz. After reading this i feel x2 smarter!
•  » » 6 weeks ago, # ^ |   -25 You have higher rating than me smh
•  » » » 6 weeks ago, # ^ |   +11 You have higher max rating than me. ORZ!
 » 6 weeks ago, # |   -22 lol, I just realized I should multiply part of $A$ (first element of $A$'s formula, or etc) instead of whole $A$ because this is just multiplying elementary matrix.
 » 6 weeks ago, # |   +214 This is not a tutorial. You just wrote the formula and didn't prove why it works or explain how to come up it. You might as well just post wikipedia link and nothing else. Then at least people wouldn't waste time reading your blog. And I'm very glad that coordinators rejected your "problem". It just asks to apply the formula and doesn't require any thinking. Problem F from 2018-2019 ACM-ICPC, Asia Nanjing Regional Contest is an okay problem which can be solved with this formula and much better than yours.
•  » » 6 weeks ago, # ^ |   -193 Thanks for wasting additional time to write this comment.
•  » » 6 weeks ago, # ^ |   0 McDic never claimed it's a tutorial. The beginning of the article says he'd like to share some nice stuff and formula itself seems a nice stuff to me. And thanks to this article we also know that it may be applied to the problem you mentioned, so I think the article is nice.
•  » » » 6 weeks ago, # ^ |   +40 I may be misremembering, but I think the title originally had [Tutorial] in it.
•  » » » » 6 weeks ago, # ^ |   +16 True, one can see this in the edit history
•  » » » » 6 weeks ago, # ^ |   +19 My bad, apologies