# Tag Info

### Real life examples of *zero* weight edges in graphs

Of course. The weight can mean things that are irrelevant to the existence of an edge. Since you don't ask for a "list of say 6 or 7 real-life examples", I will just add one. Consider a ...

### How can I quickly judge whether matrix A is the inverse matrix of B?

You might be looking for something like Freivalds' algorithm. It is a randomized probabilistic algorithm that given three square matrices $A,B$ and $C$ checks if $A \times B = C$ by using random ...
Accepted

### In algorithms for matrix multiplication (eg Strassen), why do we say n is equal to the number of rows and not the number of elements in both matrices?

Here, n = 8 and we are doing n = 8 multiplications and n/2 = 4 additions. So even a naïve multiplication algorithm would yield a time complexity of O(n). That is wrong. It might work for a small ...

### Time complexity of comparing two $N \times N$ Matrices?

A very simple adversary argument shows that when comparing two vectors of length $M$ (in your case, $M = N^2$), you must query (in the worst case) all positions of both vectors to know whether they ...
Simplifying the problem: Given a positive integer $r$ positive integers $m, n \geq 2$ a partial binary matrix $\mathrm A \in \{*, 0,1\}^{m \times n}$ (where $*$ denotes an unknown entry)...