# Questions tagged [matrices]

For questions about construction and modification of matrices, objects represented by 2-dimensional arrays that are used to define linear operators within linear algebra.

298 questions
Filter by
Sorted by
Tagged with
1 vote
45 views

### Counting the number of parenthesization

I'm reading CLRS and there is something I don't understand regarding counting the number of parenthesization, in the Matrix-chain multiplication chapter, the book says: Denote the number of ...
1 vote
28 views

### Complexity of finding $d$ largest eigenvectors of a symmetric matrix

I know that for $n \times n$ matrix, it takes $O(n^2)$ time complexity to compute the largest eigenpair of the matrix using Power method or etc. I'm interested to further extend the case so that now ...
50 views

### What kind of algorithm do i need when the place of numbers changing according to n number?

I have a project in Golang. But i don't have any idea about how to solve it. n will be an odd number (Feedback will be given if an odd number is not written) As output, a structure with n*n matrix ...
1 vote
20 views

### Algorithmic ideas to multiply two tall & skinny matrices into one large square matrix?

This problems comes from AI, and it looks something like this: I am supposed to multiply two floating-point matrices A * B. A ...
11 views

### runtime of solving matrix differential equation wrt dimensions of matrix

Suppose a computer solves a coupled differential equations (with given boundary conditions) of which each equation deals with $2^n \times 2^n$ size of matrices as solutions. My question is Does time-...
49 views

### Low-rank matrix completion is NP-hard

In looking into the problem of low-rank matrix completion / relaxations of the general problem to derive exact solutions, many papers cite that the original formulation is NP-hard but I cannot find a ...
1 vote
17 views

87 views

### Data structure to efficiently add zero-rows to a sparse matrix

I would like to create a data structure representing a sparse matrix, where the number of non-zero values is $\mathcal{O}(n)$ (the matrix is $n\times n$). The matrix should support the following ...
1 vote
43 views

### Describing the subproblem graph for matrix-chain multiplication

From Introduction to Algorithms by CLRS: 15.2-4 Describe the subproblem graph for matrix-chain multiplication with an input chain of length n. How many vertices does it have? How many edges does it ...
61 views

### minimizing a pairwise sum with respect to a sequence of integers

Let $m$ and $n$ be two integers, where $m \leq n$. Suppose you are given $m^2$ matrices $W^{i,j} \in \mathbb{R}^{n \times n}$ for $i, j \in \{1, \dots, m\}$. The goal is to find a sequence $a$ of $m$ ...
574 views

### Optimizing a sum of matrix chains

Edit Jan 31: important special case is when the sums form a nested structure, search for "Hasse diagram is a tree" below Here's a practically relevant variation on matrix chain problem: Find ...
78 views

### Best-known complexity for $l \times m$ by $m \times n$ matrix multiplication?

I know that the fastest known algorithm for multiplying two $m \times m$ matrices runs in time $m^{\omega}$, where currently we have $\omega = 2.3728596$ due to Virginia Williams's latest result (see ...
4k views

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

The meaning of edges with zero weight in a weighted graph questions me for a long time, and I even asked a related question previously. Yet, when I recently read here a question on real life example ...
81 views

### Is it NP-hard to find different roots of different matrices simultaneously?

Consider the following problem: input: pairwise distinct natural numbers $k_1,\dots,k_m$ that are all $\leq n$, and matrices $A_1,\dots,A_m \in \Bbb Q^{n \times n}$ where $m \leq n$. output: a ...
1 vote
51 views

### A hash function for a 2D hash table with a scattering property?

I have an $n\times n$ matrix, and want to find a bijective function $h:[n^2] \to [n]\times [n]$ that can act as a hash function to map the numbers 1 through $n^2$ to row/column indices in my matrix. ...
121 views

### Computing tr(ABCD...)

Suppose we have $k$ $n\times n$ matrices $A,B,C,\ldots$. Is there a way to compute/approximate the trace of their product much faster than computing/approximating the full matrix product? IE, ...
63 views

### Cover 2 by n binary matrix with submatrices of minimum total size

This is a homework problem. Let $A$ be an input binary matrix of size $2 \times n$, and $L$ an integer. The objective is to cover all 1s in $A$ with submatrices, such that we minimize the sum of the ...
66 views

### N points with maximum sum distance

Given a distance matrix for 50,000 points, how do I select $N$ points so that the sum of all distances between the $N$ points is maximized? $N$ could be as high as 100. To calculate the sum of ...
201 views

### Algorithm that finds a matrix with a specific number of 1s in its rows & columns

Question: Given integer $n \geq 2$ and two lists of size $n$, $A$ and $B$, of non-negative integers, determine if there exists an $n \times n$ matrix whose $i$-th row has $A[i]$ $1$s and whose $j$-th ...
1 vote
35 views

### Variation on Matrix Chain problem -- compute diagonal only?

How would you get an optimal schedule to solve matrix chain problem where you only need to obtain the diagonal? (assuming the resulting matrix is square) First computing the matrix product and then ...
70 views

### Longest sequence of 1s in a binary matrix

I would like a hint for this homework question. The problem is to come up with a divide and conquer solution for finding the maximum sequence of 1s in a given a binary matrix of order $n$. The ...
54 views

### Prove Permutation approach of finding best paranthesization to matrix chain multiplication is $4^n$

Suppose we have matrices $A_0,⋯,A_{n−1}$ (you can say $n$ matrices). Matrix $A_i$ is with dimension $d_i\times d_{i+1}$. If we would like to find all possible permutations to find the best ...
35 views

### Finding sequences in a binary matrix with recursion

Given a binary square matrix of order $n$. Can the problem of finding the longest sequence of 1's (horizontal or vertical) be solved with recursion? I know how to solve the problem without recursion ...
1 vote
52 views

### What is the space-complexity of the Newton-Raphson algorithm?

What's the space-complexity of Newton-Raphson? I think it reduces to the space-complexity of storing the inverse hessian matrix.
I've been looking for an algorithm to tell the number of non-zero rows (or columns) in a row reduces matrix $A\in \mathbb{R}^{m\times n}$. A simple approach would be to check it, row by row, which ...