25
votes
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 ...
- 15.5k
24
votes
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 ...
- 616
20
votes
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 ...
- 1,585
18
votes
How to prove that matrix inversion is at least as hard as matrix multiplication?
If you want to multiply two matrices $A$ and $B$ then observe that
$$\begin{pmatrix}I_n&A&\\&I_n&B\\&&I_n\end{pmatrix}^{-1}=
\begin{pmatrix}I_n&-A&AB\\&I_n&-B\\&...
- 1,181
13
votes
Accepted
Fastest way to solve a system of linear equations
A LU decomposition of a $n \times n$ matrix can be computed in $O(M(n))$ time, where $M(n)$ is the time to multiply two $n \times n$ matrices. Therefore, you can find a solution to a system of $n$ ...
D.W.♦
- 156k
12
votes
Real life examples of *zero* weight edges in graphs
The classic strategy game Civilization by MicroProse represents the world map as a square grid where each node of the grid is a tile of the world map, representing some type of terrain. Players ...
- 1,227
11
votes
Accepted
Minimal basis for set of binary vectors using XOR
If you treat your vectors as over the field $GF(2)$ rather than over the set $\{0,1\}$, then what you ask is to find a basis for the span of a set of vectors. This is a well-studied problem in linear ...
- 275k
9
votes
Real life examples of *zero* weight edges in graphs
In circuity, we often construct a graph of a circuit. Wires are typically modeled as 0 resistance because, frankly, measuring the resistance of wires is really tricky and rarely profitable. So if we ...
- 3,241
9
votes
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?
Short answer: because it's natural and convenient.
Longer answer: The number of multiplications to multiply a matrix of size p,q with a matrix of size q,r is pqr with a naive algorithm, and something ...
- 346
8
votes
How can I quickly judge whether matrix A is the inverse matrix of B?
tl;dr: You can make a rough probabilistic judgement in $O(1)$ time
Let's assume you are willing to settle on a test which differentiates "good" matrices $A,B$ from "pretty bad" $A,...
- 955
7
votes
Accepted
Recursive definition of Matrix
Multiple Dimensions
For a recursive counterpart for matrices, we need dependent types.
Indeed, lists are one dimensional and so (horizontal) concatenation of lists is all that is needed. However, ...
- 884
7
votes
Accepted
Choosing nonzero entries from an array so no pair in same row or column
The Birkhoff–von Neumann theorem states that a doubly stochastic matrix (a matrix with non-negative entries in which rows and columns sum to 1) can be written as a convex combination of permutation ...
- 275k
7
votes
Suitable choice for moderate-size square matrix multiplication?
Dumas and Pan recently wrote a non-asymptotic survey of fast matrix multiplication in practice, which hopefully answers your questions. They concentrate on matrices of order at most a million, and ...
- 275k
7
votes
Accepted
6
votes
Accepted
Correctness of Freivald algorithm for checking matrix multiplication, why is the probability of checking $AB \neq C$ at least 1/2?
Let $G$ be the number of good vectors, and $B$ be the number of bad vectors. The proof shows that $G \geq B$, since the mapping from the bad vectors to the good ones is one-to-one. Since all vectors ...
- 275k
6
votes
Accepted
Is matrix "adjoint-squaring" faster than general matrix multiplication?
It's not faster (asymptotically). You can reduce general matrix multiplication down to three "adjoint-squarings".
Suppose we're given an adjoint-squaring function $\mathfrak{F}$ where $\mathfrak{F}(M)...
- 5,802
6
votes
Counting islands in Boolean matrices
Orlp gives a solution using $O(n)$ words of space, which are $O(n\log n)$ bits of space (assuming for simplicity that $n=m$). Conversely, it is easy to show that $\Omega(n)$ bits of space are needed ...
- 275k
6
votes
Lower Bound of Matrix Multiplication
Strassen, in his paper describing Strassen's algorithm (Gaussian elimination is not optimal) mentions
the result of Klyuyev and Kokovkin-Shcherbak [1] that Gaussian elimination for solving a system ...
- 275k
6
votes
Given a row sum vector and a column sum vector, determine if they can form a boolean matrix
This problem is known as discrete tomography, and in your case two-dimensional discrete tomography. A nice approachable introduction is written Arjen Pieter Stolk's thesis Discrete tomography for ...
- 12.7k
6
votes
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?
For n = 100, the naive algorithm takes 1,000,000 multiplications and almost as many additions. If we let n = number of rows / columns, then it takes $n^3$ multiplications and $n^3 - n^2$ additions. If ...
- 28.3k
5
votes
Accepted
Finding trading cycles
I'm assuming that items are always traded 1-for-1.
How do I find the longest possible series (or path) of supply & demand matching among some people and therefore can foster an exchange?"
If ...
- 497
5
votes
Accepted
Are there parallel matrix exponentiation algorithms that are more efficient than sequential multiplication?
If you have multiple processors that can work in parallel, then you can calculate any power up to the power (2^k) in k steps. For example: To calculate $M^{15}$, you calculate:
Stage 1: Calculate $M^...
- 28.3k
5
votes
Accepted
Common idea in Karatsuba, Gauss and Strassen multiplication
The classical framework is the one of bilinear algorithms and tensor rank decompositions; basically, you construct the 3-way tensor associated to the bilinear map $f(A,B) = A \cdot B$, in the basis of ...
- 254
5
votes
Fastest way to solve a system of linear equations
There is what you want to achieve, and there is reality, and sometimes they are in conflict. First you check if your problem is a special case that can be solved quicker, for example a sparse matrix. ...
- 28.3k
5
votes
How does matrix chain multiplication problem has an optimal substructure?
First of all, it is correct and important to know that optimal solutions need not necessarily be unique!
However, this doesn't mean we cannot have optimal substructure. Recall what optimal ...
- 7,768
5
votes
Accepted
Does this algorithm for permuting rows and columns of a matrix converge?
For an $n \times m$ matrix $M$, define the potential function
$$
\Phi(M) = \sum_{i=1}^n \sum_{j=1}^m 2^{n-1-i} 2^{m-1-j} M(i,j).
$$
If we write it as
$$
\Phi(M) = \sum_{i=1}^n 2^{n-1-i} \sum_{j=1}^m 2^...
- 275k
4
votes
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 ...
- 275k
4
votes
How to reduce the low-rank matrix completion problem to integer programming?
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)...
4
votes
Are there parallel matrix exponentiation algorithms that are more efficient than sequential multiplication?
There's two levels you can analyze parallel speedups with matrix exponentiation: The "macro-algorithmic" level that decides which matrices to multiply, and the "micro-algorithmic" level where you can ...
- 743
Only top scored, non community-wiki answers of a minimum length are eligible