Skip to main content
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
  • 16.7k
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
  • 162k
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,237
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,351
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
  • 530
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
  • 995
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

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
  • 162k
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
  • 13.6k
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
  • 30.7k
6 votes
Accepted

Arrays. Find row with most 1's, in O(n)

Below is an algorithm which runs in $\mathcal{O}(1)$ memory and $\mathcal{O}(n)$ time. It accepts a $n \times n$ matrix $A$ which is $1$-indexed, follows the constraint described in the problem, and ...
EnEm's user avatar
  • 336
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
  • 30.7k
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
  • 507
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
  • 30.7k
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
  • 8,303
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
5 votes

Arrays. Find row with most 1's, in O(n)

Hint: If the first row has k 1s, and the second row has k’ 1s, then there is no need to determine k’ at all if k’ <= k. How do you find in O(1) that k’ <= k? And if k’ > k, which you checked ...
gnasher729's user avatar
  • 30.7k
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
4 votes
Accepted

$(max,+)$ matrix product with limited number of values

The paper All pairs shortest paths using bridging sets and rectangular matrix multiplication by Uri Zwick shows that the APSP problem can be solved in subcubic time, given a bound on the edge-weights. ...
Discrete lizard's user avatar
  • 8,303
4 votes
Accepted

Counting islands in Boolean matrices

Here's a sketch of an algorithm that only keeps two rows in memory at a time, so $O(m)$ memory. But since you can run this algorithm on the transpose of the matrix without issues, the actual ...
orlp's user avatar
  • 13.6k

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