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 ...
Pål GD's user avatar
  • 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 ...
phan801's user avatar
  • 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 ...
Jakube's user avatar
  • 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\\&...
Amaury Pouly's user avatar
  • 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.'s user avatar
  • 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 ...
kviiri's user avatar
  • 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 ...
Yuval Filmus's user avatar
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 ...
Cort Ammon's user avatar
  • 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 ...
Stef's user avatar
  • 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,...
einpoklum's user avatar
  • 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, ...
Musa Al-hassy's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
7 votes
Accepted

Find if there is matrix that satisfying the following conditions

Hint #1: Hint #2:
D.W.'s user avatar
  • 156k
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 ...
Yuval Filmus's user avatar
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)...
Craig Gidney's user avatar
  • 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 ...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
orlp's user avatar
  • 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 ...
gnasher729's user avatar
  • 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 ...
tjhighley's user avatar
  • 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^...
gnasher729's user avatar
  • 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 ...
Federico Poloni's user avatar
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. ...
gnasher729's user avatar
  • 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 ...
Discrete lizard's user avatar
  • 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^...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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)...
Rodrigo de Azevedo's user avatar
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 ...
Kurt Mueller's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible